[AdditionalFile5493.zip](file://AdditionalFile5493.zip?type=additional_file)

#5493. 「POI2006 R1」光盘 The Disks

标签: 传统 | 时间限制: 1000 ms | 内存限制: 32 MiB |

题目描述

题目译自 XIII OI Olimpiada Informatyczna – I etap Krążki

小 Jasio 从父母那里收到了一个新的生日玩具，其中包括一个管子和一些光盘。

这个管子的形状很特别，它是由若干个（厚度相同的）圆柱体连接而成，每个圆柱体的中心（同轴）都开有不同直径的圆孔。管子底部封闭，顶部敞开。下图展示了一个这样的管子样例，它由多个圆柱体组成，其中开凿的圆孔直径依次为：$5 \mathrm{~cm}$、$6 \mathrm{~cm}$、$4 \mathrm{~cm}$、$3 \mathrm{~cm}$、$6 \mathrm{~cm}$、$2 \mathrm{~cm}$ 和 $3 \mathrm{~cm}$。

Jasio 玩具中的光盘也是圆柱体，它们的直径各不相同，但厚度与构成管子的圆柱体厚度相同。

Jasio 给自己想了这么一个游戏。他手头有一套光盘，他想知道，如果将这些光盘按顺序精确地投入管子中心，那么最后一个光盘会停在哪个深度。举个例子，如果把直径依次为 $3 \mathrm{~cm}$、$2 \mathrm{~cm}$ 和 $5 \mathrm{~cm}$ 的光盘投入上面的管子，我们将会看到如下情景：

如您所见，每个光盘在投入后会一直下落，直到它被卡住（即当光盘的直径不小于某个圆柱体的孔径时，它会停在那个圆柱体上），或者碰到其他光盘或管底等障碍物为止。

因为这个游戏对小 Jasio 来说太难了，他总是向父母求助。而 Jasio 的父母又不太喜欢这种智力游戏，于是他们请你这位熟悉的程序员朋友编写一个程序来代替他们回答 Jasio 的问题。

请编写一个程序，实现以下功能：

• 从标准输入读取管子的结构和 Jasio 将要投入的光盘的描述信息，
• 计算出 Jasio 投入的最后一个光盘将停在的深度，
• 将结果输出到标准输出。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$ $(1 \leq n, m \leq 300000)$，由单个空格隔开，分别表示 Jasio 管子的高度（构成管子的圆柱体数量）和 Jasio 打算投入的光盘数量。

输入的第二行包含 $n$ 个整数 $r_{1}, r_{2}, \ldots, r_{n}$ $(1 \leq r_{i} \leq 1000000000)$，由单个空格隔开，表示构成管子的连续（从上到下）圆柱体中开凿的圆孔直径。

输入的第三行包含 $m$ 个整数 $k_{1}, k_{2}, \ldots, k_{m}$ $(1 \leq k_{j} \leq 1000000000)$，由单个空格隔开，表示 Jasio 打算依次投入的光盘的直径。

输出格式

输出仅一行，包含一个整数，表示最后一个光盘停止的深度。如果这个光盘根本无法进入管子，则输出 $0$。

样例

输入

7 3
5 6 4 3 6 2 3
3 2 5

输出

2