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.

Вхід завершується строкою, що містить два нулі. Це не є частиною жодного тестового випадку і не повинно оброблятися.

Вихідні дані

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