← 返回题目列表

Codeforces · 2120/E

E. 汽车车道

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

Harshith 是 TollClub 的总裁。他指派他的下属雅利安(Aryan)负责监管一个设有 $$$n$$$ 车道的收费站。最初,第 $$$i$$$ 车道有 $$$a_i$$$ 辆车在排队等候。每条车道前方每秒只有一辆车通过收费站。

汽车的愤怒度定义为通过收费站之前必须等待的秒数。考虑每辆车通过收费站需要 1 秒,即车道中的第一辆车有愤怒 $$$1$$$,第二辆车有愤怒 $$$2$$$,依此类推。

为了减少拥堵和挫败感,汽车可以变换车道。汽车可以随时立即移动到任何其他车道的后面。然而,由于变道引起的混乱,变道会额外增加 $$$k$$$ 个单位的愤怒。

Harshith 是一个了不起的人,他希望通过最大限度地减少所有汽车的总愤怒来帮助司机。他要求雅利安这样做,否则就被解雇。 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$$$ 个数字表示第 $$$i$$$ 车道中的汽车数量 ($$$1 \le a_i \le 10^6$$$)。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

请注意,所有测试用例的 $$$\max a_i$$$ 之和为 不 有界。

输出

对于每个测试用例,在新行中输出一个整数,表示最小总愤怒度。

示例

输入
复制

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

注意

在第一个测试用例中,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$$$。