题目描述

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

• 选择任意正整数 $x$，购买一个大小为 $x$ 的箱子。
• 将 $N$ 个玩具分别放入 $N$ 个箱子（包括原有的箱子和新购买的箱子）中，但每个玩具只能放入大小不小于该玩具的箱子，且每个箱子只能放一个玩具。

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

输入格式

第一行，输入一个整数 $n$。

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

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

输出格式

如果存在能满足条件的 $x$ 值，输出其最小值；否则，输出 $-1$。

translated by

https://www.luogu.com.cn/user/1030381

样例 1

输入

4
5 2 3 7
6 2 8

输出

3

样例 2

输入

4
3 7 2 5
8 1 6

输出

-1

样例 3

输入

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

输出

37