Hide

Problem F
Monument Maker

You are a stone-chiseler in Ancient Greece, charged with copying the text from famous monuments onto new stones. The existing inscriptions use boustrophedon writing, in which the lines of text alternate direction, and if a line ends in the middle of a word, the word simply continues on the next line. For example, an inscription may look like this:

IN.HONOR.OF.THE.INTERNAT
TEPMOC.GNIMMARGORP.LANOI
ITION

(In the original boustrophedon style, no spaces or punctuation were used between words, but here we have introduced periods between words.)

Today, however, you have been asked to copy these over into the new-fangled style where each line runs left to right, and words will not be split across lines — if there is not room for a whole word on a particular line, it will be started on the next line. So, the inscription above might instead look like this:

IN.HONOR.OF.THE
INTERNATIONAL
PROGRAMMING.COMPETITION

Of course, before you get started, you will need to know what size of stone will be required for your inscription. The width of the stone will be given, and the length for you to determine.

Input

The first line of the input will consist of three numbers, $n$, the number of lines in the original inscription, $d$, the width of the original inscription, and $w$, the width of your new stone in characters. Then, $n$ lines follow containing the original inscription written in boustrophedon style. You may assume that the first $n-1$ such lines consist only of capital letters and periods, with the $n$-th line also possibly containing spaces. You may assume that no two periods appear consecutively, that $1\leq n \leq 100\, 000$, $1\leq d\leq 100$, $1\leq w\leq 100$, and that no word is more than $w$ letters long.

Output

The output should consist of a single integer, representing the number of lines required to write the inscription when writing left to right and not splitting words across lines.

Sample Input 1 Sample Output 1
3 24 24
IN.HONOR.OF.THE.INTERNAT
TEPMOC.GNIMMARGORP.LANOI
ITION
3
Sample Input 2 Sample Output 2
3 24 20
IN.HONOR.OF.THE.INTERNAT
TEPMOC.GNIMMARGORP.LANOI
ITION
4
Sample Input 3 Sample Output 3
2 23 15
THIS.IS.ANOTHER.SAMPLE.
                   TXET
2

Please log in to submit a solution to this problem

Log in