Clubs 是一个由两名玩家合作以达成“最优合约”的游戏。每名玩家手中都持有若干张牌，其中一些是梅花（clubs）。每名玩家都知道自己手中梅花的数量，但不知道对方手中梅花的数量。最优合约取决于两人手中梅花的总数——如果总数小于 $X$，则最优合约为 $N$，否则为 $N + 1$。

合约通过竞价达成。第一名玩家首先提出一个合约（一个正整数）。随后玩家轮流进行操作。在自己的回合中，玩家可以选择接受上一个提出的合约，或者提出一个不同的、更高的合约（同样是一个正整数）。当其中一名玩家接受某个合约时，竞价结束；如果该合约恰好是当前的最优合约，则视为成功。

Algosia 和 Bajtek 正在玩这个游戏。他们都知道 $X$、$N$，并且知道 Algosia 手中梅花的数量是 $a_1, a_2, \dots, a_k$ 中的一个，而 Bajtek 手中梅花的数量是 $b_1, b_2, \dots, b_l$ 中的一个。在游戏开始前，每名玩家都会获知自己手中梅花的准确数量。

他们希望找到最小的 $N$，使得存在一种竞价策略能够保证游戏成功。Algosia 总是先手。可以证明，这样的最小 $N$ 是存在的。

输入格式

第一行包含三个整数 $X, k, l$ ($1 \le X \le 10^9$; $1 \le k, l \le 1000$)，分别表示使得最优合约为 $N + 1$ 所需的两人手中梅花总数的阈值，以及 Algosia 和 Bajtek 手中可能的梅花数量的个数。

第二行包含 $k$ 个整数 $a_1, \dots, a_k$ ($1 \le a_1 < a_2 < \dots < a_k \le 10^9$)，表示 Algosia 手中可能的梅花数量。

第三行包含 $l$ 个整数 $b_1, \dots, b_l$ ($1 \le b_1 < b_2 < \dots < b_l \le 10^9$)，表示 Bajtek 手中可能的梅花数量。

输出格式

输出一个整数，即能使 Algosia 和 Bajtek 保证达成最优合约的最小 $N$。

样例

样例输入 1

13 5 3
1 5 7 10 12
2 6 9

样例输出 1

3

样例输入 2

2 1 1
1
1

样例输出 2

0

说明

在第一个样例中，对于 $N = 3$，可以使用以下策略：

• 如果 Algosia 有 5, 7 或 10 张梅花，她提出合约 1。
  • 如果 Bajtek 有 6 张梅花，他回应 2。
    • 如果 Algosia 有 5 张梅花，她回应 3。Bajtek 接受（此时总数为 11）。
    • 如果 Algosia 有 7 或 10 张梅花，她回应 4。Bajtek 接受（此时总数为 13 或 16）。
  • 如果 Bajtek 有 2 张梅花，他回应 3。Algosia 接受（此时总数为 7, 9 或 12）。
  • 如果 Bajtek 有 9 张梅花，他回应 4。Algosia 接受（此时总数为 14, 16 或 19）。
• 如果 Algosia 有 1 或 12 张梅花，她提出合约 2。无论 Bajtek 手中有多少梅花，他都回应 3。
  • 如果 Algosia 有 1 张梅花，她接受（此时总数为 3, 7 或 10）。
  • 如果 Algosia 有 12 张梅花，她回应 4。Bajtek 接受（此时总数为 14, 18 或 21）。

可以证明对于 $N = 2$ 不存在合适的策略。

在第二个样例中，对于 $N = 0$，Algosia 出价 $1 = N + 1$，Bajtek 接受该合约。