Задача C. Текст

Входной файл:text.in   Ограничение времени:2 сек
Выходной файл:text.out   Ограничение памяти:256 Мб

Условие

Давным-давно, в далекой-далекой галактике учились в одной школе два закадычных друга — Вася и Петя. Они были верными товарищами, не раз выручавшими друг друга в трудную минуту из самых безвыходных ситуаций. Однако речь сейчас пойдет не об этом, а о редчайшем случае — ссоре между двумя героями нашего повествования.

В конце седьмого класса Вася увлекся программированием и написал свой текстовый редактор. Естественно, Петя тут же захотел его испытать. Несложно представить насколько велико было его разочарование, когда обнаружилось, что Васина программа корректно работает только при использовании экрана с тем же разрешением, как и у него дома. Вася оправдывал это тем, что оптимальный вывод текста на экран — штука сложная, поэтому универсальным образом сделать это невозможно. Петя же заявил, что хоть программист он и никудышный, но легко решит эту задачу.

К сожалению, программирует Петя действительно из рук вон плохо, поэтому он просит вас помочь ему в написании решения.

На вход дан текст. Назовем словом последовательность символов, ограниченную пробелами, началом или концом текста. Обратите внимание, что в данной задаче знаки препинания считаются частью слова. Требуется разбить текст на строки так, чтобы длина каждой из них была не более k символов, при этом их общее количество было минимальным. Порядок слов и сами слова менять запрещено.

Формат входного файла

Первая строка входного файла содержит натуральное число k — максимально допустимая длина строки.

Вторая строка входного файла содержит текст, который необходимо вывести. Текст состоит из латинских букв, цифр, пробелов и символов "," (запятая), "." (точка), "!" (восклицательный знак) и "?" (вопросительный знак).

Формат выходного файла

Выведите заданный во входном файле текст так, чтобы длина каждой строки была не более k символов, а количество строк было минимально возможным. Гарантируется, что задача имеет решение. В случае если решение не единственно, выведите любое из них. Слова в выходном файле должны быть отделены друг от друга пробелами и/или переводами строк.

Ограничения

1 ≤ k ≤ 100. Размер входного файла не превышает 50000 байтов.

Примеры тестов

Входной файл (text.in) Выходной файл (text.out)
1
22
This     is a sample text!
This is a sample text!
2
12
This     is a sample text!
This is a
sample text!


0.037s 0.009s 15