Рабочее место участника

Недавно Женя устроился в компанию "Гуглекс", и сегодня его первый рабочий день. Женя живет на другом берегу реки и для проезда на работу решил воспользоваться паромом. Неожиданно он обнаружил, что съехать с парома на шоссе – не такая уж простая задача.

Машины на съезде с парома стоят в `n` полос, в `i`-й из которых стоит `c_i` машин, а непосредственно перед съездом находится светофор. Раз в минуту он включается зеленым и несколько машин с парома съезжают на берег. Женя заметил, что за один зеленый сигнал светофоров количество машин, которые могут успеть проехать со всех полос, суммарно не превосходит `k`.

Понимая, что он не один такой, кому не нравится стоять в пробках, Женя ввел понятие "злости водителя". Злость водителя в некоторый момент времени равна количеству машин,которые стоят перед ним в этот момент в той же полосе. Например, если в полосе стоит 3 машины, то у водителя, чья машина находится ближе всего к светофору, злость равна 0, у следующего – 1, а у последнего – 2. Как настоящий программист, Женя сразу же начал думать, как можно оптимизировать процесс съезда с парома.

Оптимальным ему показался следующий вариант: в каждой полосе перед съездом поставить шлагбаум, который будет за один зеленый сигнал светофора пропускать только определенное количество машин. А именно, `i`-й полосе будет сопоставлено целое число `k_i` – максимальное количество машин, которые могут съехать за один зеленый сигнал. Сумма всех `k_i` должна быть равна `k`.

В качестве параметра оптимизации Женя выбрал суммарную злость всех водителей за все время съезда. Каждую минуту после очередного включения зеленого света просуммируем злость всех еще не покинувших паром водителей. Просуммируем получившиеся величины за все минуты, пока хотя бы один водитель еще находится на пароме. Женя хочет подобрать `k_i` таким образом, чтобы получившаяся величина была минимальна.

Пока Женя стоит в пробке, помогите ему написать программу, находящую оптимальные `k_i`, чтобы он смог оправдаться перед начальством за опоздание в первый же рабочий день.

В первой строке входного файла содержатся два числа `n`, `k` (`1\ ≤\ n\ ≤\ k\ ≤\ 300`) – количество полос на пароме и ограничение на количество машин, проезжающих за один зеленый сигнал светофора со всех полос.

Во второй строке входного файла находятся `n` чисел `c_i` (`1\ ≤\ c_i\ ≤\ 100\ 000`) – количество машин, стоящих в `i`-й полосе в начальный момент времени.

В первой строке выходного файла выведите число `a` – минимальную суммарную злость всех водителей за все время движения машин через светофоры.

В следующей строке выведите `n` натуральных чисел `k_i` – ограничения на количество машин, проезжающих за один зеленый сигнал, для каждой полосы. Сумма чисел должна быть равна `k`. Если оптимальных решений несколько, можно вывести любое.

3 4
1 2 4

1
1 1 2

3 4
1 2 6

7
1 1 2

В первом тестовом примере в оптимальном ответе за первый зеленый сигнал светофоров через первый шлагбаум проедет 1 машина, через второй – 1, через третий – 2. После этого злость оставшихся водителей будет равна `0+1+0=1` (в первом ряду не осталось машин, во втором ряду осталась одна машина, злость ее водителя равна 0, в третьем ряду осталось две машины, злость водителей в них равны 1 и 0). За второй зеленый сигнал светофоров проедут все оставшиеся машины. Получаем, что суммарная злость всех водителей за все время движения машин равна 1.

Во втором тестовом примере оптимальные числа `k_i` такие же, однако суммарная злость водителей другая. После первого зеленого сигнала светофоров на первой полосе не останется машин, на второй полосе останется одна машина, злость ее водителя будет равна 0, а на третьей полосе останется 4 машины, злость водителей будет равна 3, 2, 1 и 0. После второго зеленого сигнала светофора на первой и второй полосах не останется машин, а на третьей полосе останется 2 машины, злость их водителей будет равна 1 и 0. После третьего зеленого сигнала машин на пароме не останется. Итого, суммарная злость водителей за все время равна `0+3+2+1+0+1+0=7`.