Пирожные

Санта Клаус планирует принести подарки на новый год n ребятам. У него есть m пирожных, и он собирается подарить каждому ребенку несколько пирожных. Однако неожиданно возникла проблема. Детям не нравится, когда кому-то достается больше пирожных, чем ему.

Каждый ребенок характеризуется своей жадностью, жадность i-го ребенка равна g_i. Если a_i ребят получат больше пирожных чем i-й, то его неудовлетворенность будет равна g_i∙a_i.

Теперь у Санты проблема: надо поделить пирожные между ребятами так, чтобы суммарная неудовлетворенность была минимальна. Каждый ребенок должен получить хотя бы одно пирожное. Санта собирается раздать все m пирожных. Помогите ему распределить их между ребятами!

Входные данные

Первая строка входного файла INPUT.TXT содержит числа n и m (1 ≤ n ≤ 30, n ≤ m ≤ 5000). Вторая строка содержит n целых чисел g₁, g₂, ..., g_n (1 ≤ g_i ≤ 10⁷).

Выходные данные

На первой строке выходного файла OUTPUT.TXT выведите минимально возможную суммарную неудовлетворенность. Вторая строка должна содержать n целых чисел: сколько пирожных следует дать каждому ребенку. Если решений несколько, то выведите любое.

Примеры

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]