高桥的纸牌接龙

题目描述

高桥手中有 $N$ 张卡片。对于 $i = 1, 2, \ldots, N$,第 $i$ 张卡片上写着一个非负整数 $A_i$。

首先,高桥会从手中自由选择一张卡片放到桌上。 然后,他会按自己的意愿重复以下操作任意次(也可以为 $0$ 次)。

设 $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

假设他先把第 4 张卡片(写着 5)放到桌上,然后进行以下操作。

• 把第 5 张卡片(写着 5)放到桌上。
• 把第 8 张卡片(写着 6)放到桌上。
• 把第 2 张卡片(写着 0)放到桌上。
• 把第 7 张卡片(写着 0)放到桌上。

此时,第 1、3、6、9 张卡片会留在手中,它们上面整数之和为 $3 + 2 + 3 + 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 \le N \le 2 \times 10^5$
• $2 \le M \le 10^9$
• $0 \le A_i \lt M$
• 输入中的所有值均为整数。