Главный журнал города предлагает своим читателям опцию публикации любого объявления на своих страницах. Отформатированное для журнала объявление выглядит следующим образом:
Через пробел записаны непустые слова из строчных и заглавных латинских букв.
В некоторых словах также стоят символы дефиса '-', означающие, что можно сделать перенос в данном слове сразу после дефиса. В слове может быть более одного дефиса.
Гарантируется, что никакие два пробела, два дефиса не стоят рядом. Пробел не стоит рядом с дефисом. Перёд первым словом и после последнего слова не стоят ни дефисы, ни пробелы.
При переносе часть слова до дефиса и сам дефис остаются на текущей строке, а оставшаяся часть слова переносится на следующую строку. Перенос также может осуществляться и между словами, тогда символ пробела остается на текущей строке. Смотрите примечание для лучшего понимания.
Объявление в журнале может занимать не более k строк и должно иметь наименьшую возможную ширину. Ширина объявления определяется максимальным количеством символов в строке (считаются буквы, пробелы и дефисы) в нем.
Напишите программу, которая определит минимальную ширину объявления.
Примечание
Для наглядности все пробелы заменены точками.
В первом примере после применения всех переносов один из возможных вариантов объявления выглядит так:
garage.
for.
sa-
le
Во втором примере:
Edu-ca-
tion-al.
Ro-unds.
are.so.fun