Таня планирует разобрать свой книжный шкаф. В шкафу есть \(n\) полок для книг, на \(i\)-й полке лежит \(a_i\) книг. Таня будет довольна, если на каждой полке будет лежать не более \(k\) книг.
Таня может совершать одну из двух операций, чтобы достичь желаемого:
- Выбрать ровно одну книжную полку и убрать все книги с нее в кладовку (то есть выбрать некоторое \(i\) и присвоить \(a_i := 0\)). На эту операцию она тратит \(x\) секунд.
- Взять все книги со всех \(n\) полок и распределить их по всем \(n\) полкам равномерно (определение этого понятия написано ниже). На эту операцию она тратит \(y\) секунд.
Рассмотрим последовательность \(a\) из \(n\) целых чисел. Тогда ее равномерное распределение — это такая последовательность \(b\) из \(n\) целых чисел, что сумма \(b\) равна сумме \(a\), а значение \(max(b) - min(b)\) минимально возможное.
Например, если массив \(a=[5, 4, 3]\), то его равномерное распределение — это \(b=[4, 4, 4]\). Если \(a=[1, 2, 3, 4]\), то его равномерное распределение — это \(b=[2, 3, 3, 2]\) (или любая другая перестановка этого массива).
Ваша задача — найти минимальное количество секунд, за которое Таня сможет получить книжный шкаф с не более чем \(k\) книгами на каждой полке.
Выходные данные
Для каждого набора входных данных выведите ответ — минимальное количество секунд, необходимые Тане, чтобы получить книжный шкаф такой, что на каждой полке стоит не более \(k\) книг.
Примечание
В первом наборе входных данных примера будет оптимальным совершить первую операцию над пятой книжной полкой. Таким образом, массив \(a\) станет равен \([1, 2, 2, 3, 5] \rightarrow [1, 2, 2, 3, 0]\).
Во втором наборе входных данных примера будет оптимальным совершить первую операцию над второй книжной полкой, а затем совершить вторую операцию. Таким образом, массив \(a\) станет равен \([1, 5, 1, 5, 5] \rightarrow [1, 0, 1, 5, 5] \rightarrow [2, 2, 3, 3, 2]\).
В третьем наборе входных данных примера будет оптимальным совершить вторую операцию. Таким образом, массив \(a\) станет равен \([1, 2, 5, 3, 5] \rightarrow [4, 3, 3, 3, 3]\).
В четвертом наборе входных данных примера будет оптимальным совершить первую операцию над первой и второй книжными полками. Таким образом, массив \(a\) станет равен \([4, 4, 1, 1] \rightarrow [0, 0, 1, 1]\).
В пятом наборе входных данных примера будет оптимальным использовать вторую операцию. Таким образом, массив \(a\) станет равен \([4, 4, 1, 1] \rightarrow [2, 3, 2, 3]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
5 4 3 5
1 2 2 3 5
5 3 4 5
1 5 1 5 5
5 4 5 6
1 2 5 3 5
4 3 2 10
4 4 1 1
4 3 10 2
4 4 1 1
4 1 5 4
1 2 1 3
|
3
9
6
4
2
9
|