You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

在一个有 $n$ 个车道的收费站中，初始时第 $i$ 个车道有 $a_i$ 辆车排队。每秒钟，每个车道最前面的1辆车通过收费站。车辆的愤怒值定义为它通过前的等待秒数（第1辆通过的车愤怒值为1，第2辆为2，以此类推）。

允许车辆随时切换到其他车道的队尾，但每次换道会使该车辆的愤怒值额外增加 $k$。请通过合理安排换道，使所有车辆的总愤怒值最小。

输入格式

• 第一行包含测试用例数 $t$（$1 \le t \le 10^4$）
• 每个测试用例：
  • 第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 2 \cdot 10^5$，$1 \le k \le 10^6$）
  • 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^6$）

输出格式

对于每个测试用例，输出最小总愤怒值。

样例输入

6
3 4
13 7 4
4 9
6 12 14 5
5 3
2 4 13 5 10
1 7
6
13 4
10 26 34 39 9 43 48 41 1 38 13 4 46
16 3
176342 171863 70145 80835 160257 136105 78541 100795 114461 45482 68210 51656 29593 8750 173743 156063

样例输出

123
219
156
21
5315
82302351405

样例解释

第一个测试用例中，最优方案是将第1车道的2辆车移到第3车道，使车辆分布变为 $[11, 7, 6]$。总愤怒值计算为：

• 各车道基础愤怒值总和：$\frac{11 \times 12}{2} + \frac{7 \times 8}{2} + \frac{6 \times 7}{2} = 66 + 28 + 21 = 115$
• 换道附加愤怒值：$2 \times 4 = 8$
• 总愤怒值：$115 + 8 = 123$

第四个测试用例中，由于只有1个车道无法换道，总愤怒值为 $\frac{6 \times 7}{2} = 21$。

数据范围