题目详情
返回题库题目描述
有 N 个玩具，编号从 1 到 N ；有 N−1 个盒子，编号从 1 到 N−1 。玩具 i (1≤i≤N) 的大小为 $A_i$ ，盒子 i (1≤i≤N−1) 的大小为$B_i$ 。
高桥想把所有玩具分别存放在不同的盒子里，他决定按以下步骤依次进行：
1、选择任意正整数 x ，购买一个大小为 x 的盒子。
2、将每个 N 玩具放入 N 盒中(现有的 N−1 盒加上新买的盒子)。在这里，每个玩具只能放进一个大小不小于该玩具大小的盒子里，任何盒子都不能装两个或两个以上的玩具。
他想通过在步骤 1中购买一个足够大的盒子来执行步骤，但是大盒子的价格更高，所以他想购买尽可能小的盒子。
请判断是否存在一个值 x 使他可以执行步骤 2 ，如果存在，求最小值 x 。
输入描述
第一行N
第二行 $A_1,A_2,A_3...A_N$，代表N个玩具的大小
第三行$B_1,B_2,B_3...B_{N-1}$,代表N-1个盒子大小
数据范围：
- 2≤N≤2×$10^5$
- 1≤$A_i,B_i$≤$10^9$
输出描述
如果存在一个x值，使得高桥可以执行步骤2，则打印最小值x。否则，打印-1。
提示
样例1：
考虑 x=3 的情况(即他在步骤 1 中购买了一个大小为 3 的盒子)。
如果新购买的盒子叫做 4 ，那么玩具 1,…,4 的大小分别是 5 、 2 、 3 和 7 ，盒子 1,…,4 的大小分别是 6 、 2 、 8 和 3 。
因此，玩具 1 可以放在盒子 1 中，玩具 2 可以放在盒子 2 中，玩具 3 可以放在盒子 4 中，玩具 4 可以放在盒子 3 中。
另一方面，如果 x≤2 ，则不可能将所有 N 玩具分别放入不同的盒子中。因此，答案为 3 。