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