← 返回题目列表

AtCoder · agc065_a

A. 随机播放和 mod K

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

给你一个整数序列 A=(A_1,A_2,\dots,A_N) 长度 N.

您可以重新排列 A 自由。找到最大值 \sum_{i=1}^{N-1} ((A_{i+1} - A_i) \bmod K) 重新排列后即可拍摄。

在这里, x \bmod K 表示整数 y 这样 0 \le y < K 和 x - y 是以下的倍数 K。例如, -3 \bmod 8 = 5,和 9 \bmod 6 = 3.

约束

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

输入

输入由标准输入按以下格式给出:

N K
A_1 A_2 \dots A_N

输出

打印答案。


示例输入 1

3 4
0 1 2

示例输出 1

6

一种最佳解决方案是重新排列 A 进入 (2,1,0) 实现 (1 - 2) \bmod 4 + (0 - 1) \bmod 4 = 3 + 3 = 6.


示例输入 2

7 123
11 34 56 0 32 100 78

示例输出 2

638