Score : $400$ points

问题描述

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

首先，Takahashi 将任意选择一张手中的卡片并将其放在桌子上。然后，他可以重复执行以下操作任意次数（包括零次）：

• 让 $X$ 表示最后放在桌子上那张卡片上的整数。如果他的手中还包含有写有整数 $X$ 或者整数 $(X+1) \bmod M$ 的卡片，那么他可以自由选择其中一张并将它放在桌子上。这里，$(X+1) \bmod M$ 表示将 $(X+1)$ 除以 $M$ 后的余数。

请输出最终留在他手中的卡片上所写整数之和的最小可能值。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

Takahashi has $N$ cards in his hand. For $i = 1, 2, \ldots, N$, the $i$-th card has an non-negative integer $A_i$ written on it.

First, Takahashi will freely choose a card from his hand and put it on a table. Then, he will repeat the following operation as many times as he wants (possibly zero).

• Let $X$ be the integer written on the last card put on the table. If his hand contains cards with the integer $X$ or the integer $(X+1)\bmod M$ written on them, freely choose one of those cards and put it on the table. Here, $(X+1)\bmod M$ denotes the remainder when $(X+1)$ is divided by $M$.

Print the smallest possible sum of the integers written on the cards that end up remaining in his hand.

Constraints

• $1 \leq N \leq 2 \times 10^5$
• $2 \leq M \leq 10^9$
• $0 \leq A_i \lt M$
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

$N$ $M$

$A_1$ $A_2$ $\ldots$ $A_N$

Output

Print the answer.

Sample Input 1

9 7
3 0 2 5 5 3 0 6 3

Sample Output 1

11

Assume that he first puts the fourth card ($5$ is written) on the table and then performs the following.

• Put the fifth card ($5$ is written) on the table.
• Put the eighth card ($6$ is written) on the table.
• Put the second card ($0$ is written) on the table.
• Put the seventh card ($0$ is written) on the table.

Then, the first, third, sixth, and ninth cards will end up remaining in his hand, and the sum of the integers on those cards is $3 + 2 + 3 +3 = 11$. This is the minimum possible sum of the integers written on the cards that end up remaining in his hand.

Sample Input 2

1 10
4

Sample Output 2

0

Sample Input 3

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

Sample Output 3

99

update @ 2024/3/10 11:39:37