ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1427. SMS

Ограничение времени: 0.5 секунды
Ограничение памяти: 64 МБ

Вступление

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

Пример

исходные данные
10 15
On the 11-th of February, 2006 the contest "Timus Top Coders: First Challenge" is held!
результат
8
Автор задачи: Дмитрий Ковалёв, Никита Рыбак, Илья Гребнов
Источник задачи: Timus Top Coders: First Challenge