开始: 2025-04-21 00:00:00

(24-25赛季)稠州常规赛20

结束: 2025-04-24 00:00:00
当前  2025-05-11 03:31:56  类型: IOI  状态: 已经结束 

P1. 装玩具
描述

N 个玩具,编号从 1N ,以及 N-1个箱子,编号从 1N-1。玩具 i 的大小为A_i,箱子 i 的大小为B_i。小z想把所有玩具分别放入不同的箱子中。他计划按以下步骤操作:

- 选择任意正整数 x,购买一个大小为 x 的箱子。

- 将 N 个玩具分别放入 N 个箱子(包括原有的箱子和新购买的箱子)中,但每个玩具只能放入大小不小于该玩具的箱子,且每个箱子只能放一个玩具。

z想通过购买合适大小的箱子来完成第 2 步,但箱子越大价格越高,因此他想尽可能购买小箱子。请判断是否存在能满足条件的 x 值,如果存在,请输出最小值;如果不存在,请输出 -1


输入

第一行,输入一个整数 n

第二行,输入 n 个整数,分别为 A_1 \sim A_n

第三行,输入 n-1 个整数,分别为 B_1 \sim B_{n-1}


输出

如果存在能满足条件的 x 值,输出其最小值;否则,输出 -1

样例

输入

4
5 2 3 7
6 2 8

输出

3

输入

4
3 7 2 5
8 1 6

输出

-1

输入

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

输出

37
提示

本题采用捆绑测试,请不用通过-1来拿部分分

2 \leq N \leq 2\times10^5,a_i,b_i \leq 10^9


提交

题目参数
时间限制 1 秒
内存限制 128 MB
提交