3498. 出老千的 xjj

单点时限: 2.0 sec

内存限制: 256 MB

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

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

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

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

输入格式

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

第二行 $n$ 个整数 $x_1,x_2,\ldots,x_n$,表示 oxx 每种牌拥有的数量。

$1 \leq n,k,x_i \leq 10^6$。

输出格式

一个整数,表示 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 胜。

13 人解决,16 人已尝试。

19 份提交通过,共有 101 份提交。

5.5 EMB 奖励。

创建: 6 年,10 月前.

修改: 6 年,9 月前.

最后提交: 3 年前.

来源: EOJ Monthly 2018.2

题目标签