DTWW - Doing The Word Wrap

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 ≤ 108 ), and N is the number of words the text to show is made of (1 ≤ N ≤ 105). 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

Added by:Pablo Ariel Heiber
Date:2010-08-13
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 VB.NET
Resource:FCEyN UBA ICPC Selection 2007

hide comments
2024-10-07 03:24:23
more testcases:
1 10
Sed ut perspiciatis unde omnis iste natus error sit voluptatem
2 10
Sed ut perspiciatis unde omnis iste natus error sit voluptatem
3 10
Sed ut perspiciatis unde omnis iste natus error sit voluptatem
4 10
Sed ut perspiciatis unde omnis iste natus error sit voluptatem
5 10
Sed ut perspiciatis unde omnis iste natus error sit voluptatem
6 10
Sed ut perspiciatis unde omnis iste natus error sit voluptatem
7 10
Sed ut perspiciatis unde omnis iste natus error sit voluptatem
8 10
Sed ut perspiciatis unde omnis iste natus error sit voluptatem
9 10
Sed ut perspiciatis unde omnis iste natus error sit voluptatem
10 10
Sed ut perspiciatis unde omnis iste natus error sit voluptatem
-1 -1
output
62
31
21
19
15
12
12
12
12
12
2024-08-07 16:41:17
tranquilos, yo le pregunté ↓
2017-03-26 21:26:28
AC in 1 go:-) easy one with binary search..
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.