ЗАДАЧА D
Заметка в газету
| Имя входного файла: | note.in |
| Имя выходного файла: | note.out |
| Ограничение по времени: | 1 секунда |
| Ограничение по памяти: | 64 Мб |
Ты лучше скажи, как нам мальчика разыскать? Папа думал, думал, а потом сказал:
- Надо заметку в газете напечатать, что пропал мальчик. Зовут дядя Федор. И все его приметы описать. Если кто увидит, пусть нам сообщит.
Э.Успенский «Дядя Федор, пес и кот», глава 5
...И мама с папой стали писать заметку. При этом они столкнулись с проблемой: какого размера должна быть заметка, чтобы в ней уместился весь написанный текст, и за нее нужно было бы заплатить как можно меньше денег.
Дело в том, что газеты печатают заметки в виде прямоугольных блоков из некоторого числа строк и столбцов символов. Текст заметки при этом переносится по словам и выравнивается по левому краю. Площадью заметки называется произведение числа строк на число столбцов символов. Помогите маме с папой расположить текст заметки в одну или несколько строк так, чтобы площадь заметки была минимальной, если заметка может содержать не более N столбцов символов. Если существует несколько вариантов расположения с минимальной площадью, то выведите тот из них, который содержит меньшее число строк.
Входные данные
В первой строке входного файла записана строка длиной не более 250 символов – текст заметки. Текст состоит из нескольких слов, разделенных одним пробелом. Слово – это последовательность непробельных символов (с кодом ASCII больше кода пробела, равного 32). Вторая строка входного файла содержит единственное число N (1 <= N <= 80) – максимальное допустимое число столбцов символов в заметке. Максимальная длина слова в заметке не превосходит N.
Выходные данные
В выходной файл выведите заметку оптимального размера. Заметка должна состоять из одной или нескольких строк равной длины. Слова в каждой строке должны быть выровнены по левому краю, разделяться одним пробелом и при необходимости быть дополненными пробелами справа.
Пример
| note.in | note.out | Примечание |
|---|---|---|
|
|
Внимание: для удобства отображения в примере выходного файла пробелы заменены на знаки подчеркивания. Ваша программа должна выводить пробелы. |