分数: 350 点
问题陈述
有 N 玩具编号自 1 to N,和 N-1 盒子编号为 1 to N-1。 玩具 i\ (1 \leq i \leq N) 的大小为 A_i和盒子 i\ (1 \leq i \leq N-1) 的大小为 B_i.
高桥想要将所有玩具存放在单独的盒子中,他决定按顺序执行以下步骤:
- 选择任意正整数 x 并购买一盒尺寸 x.
- 将每个 N 玩具变成其中之一 N 盒( N-1 现有盒子加上新购买的盒子)。 这里,每个玩具只能放入一个尺寸不小于该玩具尺寸的盒子中,并且任何盒子都不能容纳两个或多个玩具。
他想要执行步骤 2 通过逐步购买足够大的盒子 1,但较大的盒子更贵,因此他想购买尽可能小的盒子。
判断是否存在值为 x 这样他就可以执行步骤 2,如果存在,找到这样的最小值 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 这样高桥就可以执行步骤 2,打印最小的这样 x。否则,打印 -1.
示例输入 1
4 5 2 3 7 6 2 8
示例输出 1
3
考虑以下情况 x=3 (即他购买了一盒尺寸 3 步骤 1).
如果新买的盒子叫盒子 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
无论购买什么尺寸的盒子,步骤 1,盒子里不能放玩具 2,因此无法执行步骤 2.
示例输入 3
8 2 28 17 39 57 56 37 32 34 27 73 28 76 61 27
示例输出 3
37