Text Justi?cation

Вы наняты внеземным разумом ∀ℑ¶ℵΞρ в качестве программиста для их системы набора текста. Ваша задача — разработать алгоритм для выравнивания текста.

Выравнивание текста заключается в том, чтобы сделать ширину строк как можно более равномерной, вставляя разрывы строк в подходящих местах. Вам дано множество слов, называемое параграфом, и ширина бумаги. Поскольку алгоритм автоматического переноса еще не разработан, вы не можете разрывать строку посередине слова. Также, в их языке между словами нет пробелов, поэтому вам не нужно учитывать пробелы.

Чтобы оценить, насколько хорошо текст выровнен в одной конфигурации (т.е. набор строк, созданных путем вставки разрывов строк в параграф), вы определили его стоимость следующим образом:

• Общая стоимость параграфа — это сумма стоимости каждой строки.

• Стоимость последней строки определяется как max(0, s − w).

• Стоимость остальных строк определяется как |s − w|.

где s — это сумма ширин слов в строке, а w — это ширина бумаги.

Пожалуйста, разработайте алгоритм, который принимает параграф и вычисляет конфигурацию с минимальной стоимостью.

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

Входные данные состоят из нескольких тестов.

Первая строка каждого теста содержит два положительных целых числа n и w (0 ≤ n ≤ 1000 и 0 ≤ w ≤ 1000000). n — это длина параграфа, а w — это ширина используемой бумаги. Каждая из следующих n строк содержит одно положительное целое число a_i, которое указывает ширину i-го слова в параграфе. Здесь гарантируется, что 0 ≤ a_i ≤ w.

Ввод завершается строкой, содержащей два нуля. Это не часть какого-либо теста и не должно обрабатываться.

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

Для каждого теста выведите номер теста и минимальную стоимость для параграфа.