ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

1427. SMS

Time limit: 0.5 second
Memory limit: 64 MB


Mobile technologies are going to become a part of our life. So many times you have read this sentence in advertisements and magazine articles. So many times you have heard it from fattened IT corporations presidents who grab money of deceived investors and from managers of mobile phones shops who try to sell useless smartphones at the cost of $500 a piece... Sleep tight. The age of mobility has not begun yet. Believe me, you will feel when it comes to life.
One day it will be felt by the millions of people who would find their mobile phones full of dozens of SMS messages offering sweets with swastika, courses of american Russian, services of famous charlatan Ilya German and participation in forthcoming contests on Timus Online Judge. Unfortunately the history will not keep the name of one modest programmer who was in the very origin of new age technology which will be known soon as SMS-spam. But I will say something else. This programmer is you.


SMS-spam is a promising technology of mass delivery of text advertisements by means of SMS messages. Very convenient, very effective, very easy. Not so easy, however. The problem is the length of one SMS message is limited while advertisements are usually rather long. Fortunately, an advertisement can be divided into several parts, and each part will be sent as a separate SMS message.
But here greedy mobile operators enter the game, because they also want to get some money. Their acquisitiveness is expressed in the fact that each delivered SMS message must be paid for. So an advertisement should be delivered to a thankful recipient by means of minimal number of SMS messages.
And the last thing. Quirky mobile operators have invented an amusing feature for people who want to save some money. SMS message which consists of latin letters and spaces only can be up to M characters long while the length of SMS message which consists of any characters is limited by N characters.


The first line contains the integer numbers N and M (1 ≤ N ≤ M ≤ 10000). The second line contains an advertisement. The advertisement consists of from 1 to 100000 characters. Each character is either a latin letter, a space, a digit or a punctuation mark "." (full stop), "," (comma), ";" (semicolon), ":" (colon), "!" (exclamation mark), "?" (question mark), "-" (hyphen) or """ (double quotes). The advertisement is terminated by the end of line.


You should output the minimal number of SMS messages required to deliver the advertisement.


10 15
On the 11-th of February, 2006 the contest "Timus Top Coders: First Challenge" is held!
Problem Author: Dmitry Kovalioff, Nikita Rybak, Ilya Grebnov
Problem Source: Timus Top Coders: First Challenge