Takahashi's Solitaire

题目描述

Takahashi 手中有 $N$ 张牌。 对于 $i = 1, 2, \ldots, N$，第 $i$ 张牌上写着一个非负整数 $A_i$。 首先，Takahashi 将自由地从手中选择一张牌并把它放到桌子上。 然后，他将重复以下操作任意次（可能为零次）。

设 $X$ 为最后放到桌子上的那张牌上写的整数。如果他的手中有写着整数 $X$ 或整数 $(X+1)\bmod M$ 的牌，则可以自由选择其中一张并把它放到桌子上。这里，$(X+1)\bmod M$ 表示 $(X+1)$ 除以 $M$ 的余数。

输出最后留在他手中牌上写的整数之和的最小可能值。

输入格式

输入从标准输入按照以下格式给出： $N$ $M$ $A_1$ $A_2$ $\ldots$ $A_N$

输出格式

输出答案。

9 7
3 0 2 5 5 3 0 6 3

11

1 10
4

0

20 20
18 16 15 9 8 8 17 1 3 17 11 9 12 11 7 3 2 14 3 12

99

提示

$1 \leq N \leq 2 \times 10^5$ $2 \leq M \leq 10^9$ $0 \leq A_i \lt M$ 输入中的所有数值均为整数。假设他首先把第四张牌（写着 $5$）放到桌子上，然后执行以下操作。

把第五张牌（写着 $5$）放到桌子上。 把第八张牌（写着 $6$）放到桌子上。 把第二张牌（写着 $0$）放到桌子上。 把第七张牌（写着 $0$）放到桌子上。

那么，第 1、3、6、9 张牌将最终留在他的手中，这些牌上整数的和为 $3 + 2 + 3 +3 = 11$。 这是留在手中的牌上整数之和的最小可能值。

标签: AtCoder|abc277D

来源

AtCoder|abc277D