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 гарантирует, что всегда существует оформление, удовлетворяющее условиям.
Последний набор данных завершается строкой, содержащей два нуля.
Выходные данные
Для каждого набора данных выведите минимально возможное количество самых длинных подряд идущих пробелов между словами.