Харшит — президент TollClub. Он поручает своему подчинённому Ариану следить за пунктом взимания платы с $$$n$$$ полосами. Изначально в $$$i$$$-й полосе стоит в очереди $$$a_i$$$ машин. Ровно одна машина с начала каждой полосы проезжает через пункт оплаты каждую секунду.
Злость машины определяется как количество секунд, которое ей пришлось ждать перед проездом через пункт оплаты. Считайте, что на проезд каждой машины требуется 1 секунда, то есть первая машина в полосе имеет злость $$$1$$$, вторая — $$$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$$$, где $$$i$$$-е число обозначает количество машин в $$$i$$$-й полосе ($$$1 \le a_i \le 10^6$$$).
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Обратите внимание, что сумма $$$\max a_i$$$ по наборам входных данных не ограничена.
Для каждого набора входных данных выведите в отдельной строке одно целое число — минимально возможную суммарную злость.
63 413 7 44 96 12 14 55 32 4 13 5 101 7613 410 26 34 39 9 43 48 41 1 38 13 4 4616 3176342 171863 70145 80835 160257 136105 78541 100795 114461 45482 68210 51656 29593 8750 173743 156063
123 219 156 21 5315 82302351405
В первом наборе входных данных Ариан перемещает две машины из полосы $$$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$$$.
