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

Timus Top Coders: First Challenge

About     Problems     Submit solution     Judge status     Standings
Contest is over

G. SMS

Time limit: 0.5 second
Memory limit: 64 MB

Background

Mobile technologies are going to become a part of our life. So many times you have read this sentence in advertisements and magazine articles. 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 chocolate bars with mushrooms, 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.

Problem

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 mobile operators enter the game: 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. The maximum length of an SMS message depends on the characters it consists of. 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.

Input

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.

Output

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

Sample

input
10 15
On the 11-th of February, 2006 the contest "Timus Top Coders: First Challenge" is held!
output
8
Problem Author: Dmitry Kovalioff, Nikita Rybak, Ilya Grebnov
Problem Source: Timus Top Coders: First Challenge
To submit the solution for this problem go to the Problem set: 1427. SMS