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

В один из дней это почувствуют миллионы, поутру обнаружив в своих мобильных телефонах десяток-другой SMS сообщений от товарищей, предлагающих купить шоколадки с мухоморами, посетить курсы американского русского, сходить к известному шарлатану Илье Герману и принять участие в очередном контесте на Timus Online Judge. Увы, история не сохранит имя скромного программиста, стоявшего у истоков революционной технологии, которая в недалёком будущем станет известна как SMS-спам. Но я скажу Вам кое-что ещё. Этот программист - Вы.

SMS-спам – это перспективная технология массовой рассылки рекламных текстов в виде SMS сообщений. Очень удобно, очень эффективно, очень просто. Впрочем, не совсем просто. Вся проблема в том, что длина одного SMS сообщения ограничена, а рекламные тексты могут быть весьма длинными. К счастью, рекламный текст может быть разбит на несколько частей, каждая из которых будет отправлена в виде отдельного SMS сообщения.

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

Чуть не забыл. Максимальная длина SMS сообщения зависит от используемых в нем символов. SMS сообщение, содержащее только латинские буквы и пробелы, может достигать целых M символов в длину, в то время как длина SMS сообщения, содержащего произвольные символы, ограничена всего N символами.

Первая строка содержит целые числа N и M (1 ≤ N ≤ M ≤ 10000). Вторая строка содержит рекламный текст. Рекламный текст имеет длину от 1 до 100000 символов и содержит только латинские буквы, пробелы, цифры и знаки препинания "." (точка), "," (запятая), ";" (точка с запятой), ":" (двоеточие), "!" (восклицательный знак), "?" (вопросительный знак), "-" (дефис) и """ (двойные кавычки). Рекламный текст заканчивается переводом строки.

Вывести минимальное количество SMS сообщений, в виде которых можно отправить исходный рекламный текст.