Beautiful Spacing
Текст — це послідовність слів, де кожне слово складається з символів. Ваше завдання — розмістити ці слова в сітку з W стовпцями та достатньою кількістю рядків. Для естетичного оформлення мають бути дотримані наступні умови.
1. Слова повинні зберігати свій початковий порядок у тексті. Нижче наведено приклади правильного та неправильного оформлення для тексту з 4 слів "This is a pen" у 11 стовпців.
2. Між двома сусідніми словами в одному рядку повинен бути принаймні один пробіл. Іноді може знадобитися більше одного пробілу, щоб виконати інші умови.
Рисунок 3: НЕПРАВИЛЬНО — Слова повинні бути розділені пробілами.
3. Кожне слово повинно займати стільки ж послідовних стовпців, скільки символів у ньому. Не можна розбивати слово на частини, розділяючи його на рядки або вставляючи пробіли.
Рисунок 4: НЕПРАВИЛЬНО — Символи в одному слові повинні бути суміжними.
4. Текст повинен бути вирівняний по обидва боки. Тобто, перше слово в рядку повинно починатися з першого стовпця, а останнє слово, за винятком останнього рядка, повинно закінчуватися на останньому стовпці.
Рисунок 5: НЕПРАВИЛЬНО — Рядки повинні бути вирівняні як зліва, так і справа.
Текст вважається найкраще оформленим, коли немає надмірно довгих пробілів. Наприклад, оформлення на Рисунку 6 має максимум 2 суміжних пробіли, що є більш естетичним, ніж на Рисунку 1, де є 3 суміжних пробіли. Дано вхідний текст і кількість стовпців, знайдіть оформлення, при якому довжина найдовших суміжних пробілів між словами є мінімальною.
Рисунок 6: Гарне і найкрасивіше оформлення.
Вхідні дані
Вхід складається з декількох наборів даних, кожен у наступному форматі.
W N
x_1 x_2 ... x_N
W, N, і x_i — це всі цілі числа. W — це кількість стовпців (3 ≤ W ≤ 80000). N — це кількість слів (2 ≤ N ≤ 50000). x_i — це кількість символів у i-му слові (1 ≤ x_i ≤ (W-1)/2). Зверніть увагу, що верхня межа на x_i гарантує, що завжди існує оформлення, яке задовольняє умови.
Останній набір даних супроводжується рядком, що містить два нулі.
Вихідні дані
Для кожного набору даних виведіть найменшу можливу кількість найдовших суміжних пробілів між словами.