#P18371. Clubs

Clubs

Clubs

Clubs 是一个双人合作游戏。两人各自手中有一些牌,其中一部分是梅花牌。每个人知道自己有多少张梅花牌,但不知道对方有多少张。

最优合同由两人梅花牌的总数决定:总数小于 XX 时,最优合同为 NN;否则,最优合同为 N+1N+1。

两人通过叫价确定合同。第一位玩家先提出一个正整数作为合同。之后两人轮流行动。轮到一名玩家时,他可以接受上一次提出的合同,或者提出一个严格更大的正整数合同。有人接受合同后游戏结束;只有结束时的合同恰好等于最优合同,才算成功。

Algosia 和 Bajtek 正在玩这个游戏。两人都知道 X,NX,N,也都知道:Algosia 的梅花牌数量是 a1,a2,…,aka_1,a_2,\ldots,a_k 中的一个,Bajtek 的梅花牌数量是 b1,b2,…,blb_1,b_2,\ldots,b_l 中的一个。游戏开始前,每个人只获知自己实际持有的梅花牌数量。

求最小的 NN,使两人存在一种叫价策略,对所有可能的牌数组合都能保证成功。Algosia 始终先手。可以证明这样的最小值一定存在。

注意:本题只要求输出这个最小的 NN,不需要模拟交互或输出策略。NN 可以为 0,但每次提出的合同仍必须是正整数。

输入格式

第一行包含三个整数 X,k,lX,k,l,分别表示使最优合同变为 N+1N+1 的梅花牌总数下界,以及两人各自可能的梅花牌数量的个数。

第二行包含严格递增的 kk 个整数 a1,…,aka_1,\ldots,a_k。

第三行包含严格递增的 ll 个整数 b1,…,blb_1,\ldots,b_l。

输出格式

输出一个整数,表示能够保证达成最优合同的最小 NN。

数据范围

  • 1≤X≤1091\le X\le10^9;
  • 1≤k,l≤10001\le k,l\le1000;
  • 1≤a1<a2<⋯<ak≤1091\le a_1<a_2<\cdots<a_k\le10^9;
  • 1≤b1<b2<⋯<bl≤1091\le b_1<b_2<\cdots<b_l\le10^9。

输入只有一组数据。

样例输入 1

13 5 3
1 5 7 10 12
2 6 9

样例输出 1

3

样例输入 2

2 1 1
1
1

样例输出 2

0

样例说明

第一个样例中,N=3N=3 时可以使用以下策略。

若 Algosia 有 5、7 或 10 张梅花牌,她先提出合同 1:

  • 若 Bajtek 有 6 张,他提出合同 2。此时 Algosia 若有 5 张,就提出合同 3,由 Bajtek 接受,两人共 11 张;若她有 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 张;若她有 12 张,就提出合同 4,由 Bajtek 接受,两人共 14、18 或 21 张。

可以证明 N=2N=2 时不存在保证成功的策略。

第二个样例中,N=0N=0。Algosia 提出合同 1=N+11=N+1,Bajtek 接受即可。