再准备一个盒子

题目描述

有 $N$ 个玩具,编号从 $1$ 到 $N$,还有 $N-1$ 个盒子,编号从 $1$ 到 $N-1$。 玩具 $i$($1 \le i \le N$)的大小为 $A_i$,盒子 $i$($1 \le i \le N-1$)的大小为 $B_i$。

高桥君想把所有玩具分别装进不同的盒子中,他决定按以下步骤依次执行:

1. 选择一个任意的正整数 $x$,购买一个大小为 $x$ 的盒子。
2. 将 $N$ 个玩具分别放入 $N$ 个盒子中($N-1$ 个已有的盒子加上新购买的盒子)。 这里,每个玩具只能放入大小不小于该玩具大小的盒子,且每个盒子不能放入两个或两个以上的玩具。

他希望在步骤 1 中购买一个足够大的盒子来执行步骤 2,但盒子越大越贵,所以他希望购买尽可能小的盒子。

判断是否存在一个 $x$ 使得他可以执行步骤 2,如果存在,求出最小的这样的 $x$。

输入格式

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

$N$
$A_1$ $A_2$ $\dots$ $A_N$
$B_1$ $B_2$ $\dots$ $B_{N-1}$

输出格式

如果存在 $x$ 使得高桥君可以执行步骤 2,输出最小的这样的 $x$;否则输出 -1。

样例

4
5 2 3 7
6 2 8

3

考虑 $x=3$ 的情况(即他在步骤 1 中购买一个大小为 $3$ 的盒子)。

如果把新购买的盒子称为盒子 $4$,则玩具 $1,\dots,4$ 的大小分别为 $5$, $2$, $3$, $7$,盒子 $1,\dots,4$ 的大小分别为 $6$, $2$, $8$, $3$。 因此,玩具 $1$ 可以放入盒子 $1$,玩具 $2$ 放入盒子 $2$,玩具 $3$ 放入盒子 $4$,玩具 $4$ 放入盒子 $3$。

另一方面,如果 $x \le 2$,则无法将全部 $N$ 个玩具放入不同的盒子中。 因此,答案为 $3$。

4
3 7 2 5
8 1 6

-1

无论步骤 1 购买多大的盒子,都没有玩具能放入盒子 $2$,因此无法执行步骤 2。

8
2 28 17 39 57 56 37 32
34 27 73 28 76 61 27

37

数据范围

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