CF2120E Lanes of Cars

Harshith 是 TollClub 的主席。他让下属 Aryan 负责一个有 $n$ 个车道的收费站。最初，第 $i$ 个车道上有 $a_i$ 辆车在排队。每秒钟，每个车道最前面的 1 辆车通过收费站。 一辆车的愤怒值定义为它在通过收费站前等待的秒数。也就是说，每辆车通过收费站需要 1 秒，第一个通过的车愤怒值为 $1$，第二辆为 $2$，以此类推。 为了减少拥堵和司机的烦躁，允许车辆随时切换到其他任意车道的队尾。每次换道会让车辆的愤怒值额外增加 $k$，因为换道会让司机更加困惑。 Harshith 希望帮助司机，要求 Aryan 通过合理安排车辆换道，使所有车辆的总愤怒值最小。Aryan 可以随时让任意车辆换道（也可以不换），目标是使总愤怒值最小。请你帮 Aryan 计算在最优换道方案下，最小的总愤怒值是多少。

每个测试点包含多个测试用例。第一行为测试用例数 $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$，其中第 $i$ 个数 $a_i$ 表示第 $i$ 个车道初始有多少辆车（$1 \le a_i \le 10^6$）。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。 注意，所有测试用例中 $\max a_i$ 的总和没有上界。

对于每个测试用例，输出一行一个整数，表示最小的总愤怒值。

在第一个测试用例中，Aryan 将第 1 车道的两辆车移到第 3 车道后，数组变为 $[11, 7, 6]$。总愤怒值为 $\frac{11\cdot 12}{2}+\frac{7\cdot 8}{2}+\frac{6\cdot 7}{2}+2\cdot 4=123$。可以证明这是最小的愤怒值。 在第四个测试用例中，只有一个车道，车辆无法换道。总愤怒值为 $\frac{6\cdot7}{2}=21$。 由 ChatGPT 4.1 翻译