题目描述

给定一个长度为 $N$ 的整数序列 $A=(A_1,A_2,\dots,A_N)$。

你可以任意重新排列 $A$。请你求出重新排列后 $\sum_{i=1}^{N-1}((A_{i+1}-A_i)\bmod K)$ 可能取得的最大值。

这里，$x\bmod K$ 表示满足 $0\leq y<K$ 且 $x-y$ 是 $K$ 的倍数的整数 $y$。例如，$-3\bmod 8=5$，$9\bmod 6=3$。

输入格式

输入以如下格式从标准输入读入。

$N$ $K$ $A_1$ $A_2$ $\dots$ $A_N$

输出格式

请输出答案。

样例 1

输入

3 4
0 1 2

输出

6

样例 2

输入

7 123
11 34 56 0 32 100 78

输出

638

说明/提示

限制条件

• $2\leq N\leq 2\times 10^5$
• $1\leq K\leq 10^9$
• $0\leq A_i<K$

样例解释 1

最优的排列为 $A=(2,1,0)$，此时 $(1-2)\bmod 4+(0-1)\bmod 4=3+3=6$。

由 ChatGPT 4.1 翻译