无形的手

题目描述

苹果市场上有 $N$ 个卖者和 $M$ 个买者。

第 $i$ 个卖者愿意以 $A_i$ 日元或更高的价格卖出一个苹果(日元是日本的货币单位)。

第 $i$ 个买者愿意以 $B_i$ 日元或更低的价格买入一个苹果。

求满足以下条件的最小整数 $X$。

条件:愿意以 $X$ 日元卖出一个苹果的卖者人数,大于等于愿意以 $X$ 日元买入一个苹果的买者人数。

输入格式

输入按以下格式从标准输入给出:

$N$ $M$
$A_1$ $\ldots$ $A_N$
$B_1$ $\ldots$ $B_M$

输出格式

输出答案。

样例

3 4
110 90 120
100 80 120 10000

110

愿意以 $110$ 日元卖出的有第 $1$、$2$ 两个卖者;愿意以 $110$ 日元买入的有第 $3$、$4$ 两个买者。因此 $110$ 满足条件。

由于小于 $110$ 的整数都不满足条件,所以这就是答案。

5 2
100000 100000 100000 100000 100000
100 200

201

3 2
100 100 100
80 120

100

数据范围

• $1 \le N,M \le 2\times 10^5$
• $1 \le A_i,B_i \le 10^9$
• 所有输入值均为整数。