← 返回题目列表

AtCoder · abc376_c

F. 再准备一个盒子

中文机器翻译题面 查看原题

分数: 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.

高桥想要将所有玩具存放在单独的盒子中,他决定按顺序执行以下步骤:

  1. 选择任意正整数 x 并购买一盒尺寸 x.
  2. 将每个 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