103762: [Atcoder]ABC376 C - Prepare Another Box

Problem Statement

There are $N$ toys numbered from $1$ to $N$, and $N-1$ boxes numbered from $1$ to $N-1$. Toy $i\ (1 \leq i \leq N)$ has a size of $A_i$, and box $i\ (1 \leq i \leq N-1)$ has a size of $B_i$.

Takahashi wants to store all the toys in separate boxes, and he has decided to perform the following steps in order:

1. Choose an arbitrary positive integer $x$ and purchase one box of size $x$.
2. Place each of the $N$ toys into one of the $N$ boxes (the $N-1$ existing boxes plus the newly purchased box). Here, each toy can only be placed in a box whose size is not less than the toy's size, and no box can contain two or more toys.

He wants to execute step $2$ by purchasing a sufficiently large box in step $1$, but larger boxes are more expensive, so he wants to purchase the smallest possible box.

Determine whether there exists a value of $x$ such that he can execute step $2$, and if it exists, find the minimum such $x$.

Constraints

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq A_i, B_i \leq 10^9$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

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

Output

If there exists a value of $x$ such that Takahashi can execute step $2$, print the minimum such $x$. Otherwise, print -1.

Sample Input 1

4
5 2 3 7
6 2 8

Sample Output 1

3

Consider the case where $x=3$ (that is, he purchases a box of size $3$ in step $1$).

If the newly purchased box is called box $4$, toys $1,\dots,4$ have sizes of $5$, $2$, $3$, and $7$, respectively, and boxes $1,\dots,4$ have sizes of $6$, $2$, $8$, and $3$, respectively. Thus, toy $1$ can be placed in box $1$, toy $2$ in box $2$, toy $3$ in box $4$, and toy $4$ in box $3$.

On the other hand, if $x \leq 2$, it is impossible to place all $N$ toys into separate boxes. Therefore, the answer is $3$.

Sample Input 2

4
3 7 2 5
8 1 6

Sample Output 2

-1

No matter what size of box is purchased in step $1$, no toy can be placed in box $2$, so it is impossible to execute step $2$.

Sample Input 3

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

Sample Output 3

37

问题陈述

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

高桥想要将所有玩具分别存放在不同的盒子里，他已经决定按以下步骤进行：

1. 选择一个任意的正整数 $x$ 并购买一个大小为 $x$ 的盒子。
2. 将每个玩具放入 $N$ 个盒子中的一个（$N-1$ 个现有盒子加上新购买的盒子）。 这里，每个玩具只能放入大小不小于玩具大小的盒子中，且没有盒子可以包含两个或更多玩具。

他希望通过在第一步购买足够大的盒子来执行第二步，但是更大的盒子更贵，所以他希望购买尽可能小的盒子。

确定是否存在一个 $x$ 的值，使得他可以执行第二步，如果存在，找出这样的最小 $x$。

约束条件

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq A_i, B_i \leq 10^9$
• 所有输入值都是整数。

输入

输入从标准输入以下格式给出：

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

输出

如果存在一个 $x$ 的值，使得高桥可以执行第二步，打印这样的最小 $x$。否则，打印 -1。

示例输入 1

4
5 2 3 7
6 2 8

示例输出 1

3

考虑 $x=3$ 的情况（即他在第一步购买了一个大小为 $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 \leq 2$，则无法将所有 $N$ 个玩具放入单独的盒子中。 因此，答案是 $3$。

示例输入 2

4
3 7 2 5
8 1 6

示例输出 2

-1

无论在第一步购买什么大小的盒子，都没有玩具可以放在盒子 $2$ 中，所以无法执行第二步。

示例输入 3

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

示例输出 3

37