You are developing a visual component for a web browser. The component is known as textarea,
and its main functionality is to show a given text using one or more lines. Every textarea has
a linewidth W , which is the number of characters that can fit in a single line.
The text that needs to be shown is a sequence of words. The textarea must display the text
using lines of W characters, without breaking any word, and placing a single space between
each pair of consecutive words that are in the same line. Any number of trailing spaces may
be left at the end of each line. So the behavior of the textarea is quite simple: it keeps adding
words to a line until the next word does not fit; each time this occurs, a new line is started.
With the permanent growing in the amount of information that web pages must show, you
have to make a smart textarea that uses as little space as possible, even when dealing with very
long texts. Given a text to show and a number of lines L, you must set the linewidth W to the
minimum possible value such that the text is shown using at most L lines.

Input

The input contains several test cases, each one described in exactly two lines. The first line
of each test case contains two integers L and N separated by a single space, where L is the
maximum number of lines the textarea can have (1 ≤ L ≤ 10⁸ ), and N is the number of words
the text to show is made of (1 ≤ N ≤ 10⁵ ). The second line contains the text to show, formed
by N non-empty words of at most 25 lowercase letters each, separated by an arbitrary number
of spaces. The last line of the input contains the number −1 twice separated by a single space
and should not be processed as a test case.

Output

For each test case output a single line with an integer W representing the minimum linewidth
such that the textarea has at most L lines.

Example

Input:
1 2
hello     word
2 2
racing club
-1 -1
Output:
10
6