#ABC312C. 苹果市场

苹果市场

AT_abc312_c [ABC312C] Invisible Hand

题目描述

\hspace{15pt}在苹果市场中,有 nn 个卖家和 mm 个买家。第 ii 个卖家愿意出售的最低价格为 aia_i 日元,第 jj 个买家愿意购买的最高价格为 bjb_j 日元。

\hspace{15pt}请求出一个最低价格 xx,使得愿意以 xx 日元出售的卖家数量不少于愿意以 xx 日元购买的买家数量。

输入格式

\hspace{15pt}第一行输入两个整数 n,m(1≦n,m≦2×105)n, m \left(1 \leqq n, m \leqq 2 \times 10^5\right) 代表卖家的数量和买家的数量。

\hspace{15pt}第二行输入 nn 个整数 $a_1, a_2, \dots, a_n \left(1 \leqq a_i \leqq 10^9\right)$ 代表每个卖家愿意出售的最低价格。

\hspace{15pt}第三行输入 mm 个整数 $b_1, b_2, \dots, b_m \left(1 \leqq b_i \leqq 10^9\right)$ 代表每个买家愿意购买的最高价格。

输出格式

\hspace{15pt}在一行上输出一个整数,代表满足条件的最低价格 xx。

测试样例

3 4
110 90 120
100 80 120 10000
110
5 2
100000 100000 100000 100000 100000
100 200
201
3 2
100 100 100
80 120
100