3498. 出老千的 xjj

单测试点时限: 2.0 秒

内存限制: 256 MB

玩了一天的 oxx 和 xjj 精力不减,晚上回到宾馆后决定玩一种卡牌游戏。

游戏规则很简单:一开始,每人手中有若干不同的牌。在每一回合中,两人轮流先手,先手可以打出 张任意相同的牌,随后两人轮流出牌,每次打出 张任意相同的牌,直至双方都不出牌,该回合结束(一方不出牌时另一方可以继续出牌直至不出牌)。下一回合中换为另一人先手,直至某一回合中一人打完手上所有牌。先打完所有牌的获胜。

xjj 出了把老千,使得自己拿到了 张相同的牌,她骄傲地向 oxx 炫耀:“我这牌稳赢了,让你先手。看看你那寒酸样,再给你额外几张万能牌,可以代替任何一张牌。”

机智的 oxx 立刻发现了自己胜利的希望,他想知道他至少拿到几张万能牌就可以赢得游戏。oxx 在第一回合中是先手。

输入

第一行两个整数 , ,分别表示 oxx 手中的牌类型数以及 xjj 手中的牌数。

第二行 个整数 ,表示 oxx 每种牌拥有的数量。

输出

一个整数,表示 oxx 至少需要多少张万能牌。

样例

Input
2 4
2 5
Output
2
Input
5 6
5 2 3 4 5
Output
6

提示

样例一:
oxx 至少需要两张万能牌,使得牌数变成3张1和6张2,首先出3张1,无论 xjj 是否出牌,都无法在这一轮出完牌,而 oxx 可以连续出两次3张2。
若 oxx 变成2张1和6张2,则xjj胜,因为 oxx 必须一次出两张才在能这一轮打完,但是 xjj 可以更快打完牌。
其他少于两张的情况 oxx 都无法在一轮打完所有牌,而 xjj 第二轮可以直接打完所有牌,所以 xjj 胜。

12 人解决,13 已尝试。

17 份提交通过,共有 93 份提交。

8.7 EMB 奖励。

创建: 10 月,2 周前.

修改: 10 月前.

最后提交: 7 月,1 周前.

来源: EOJ Monthly 2018.2