MagazineAdCodeForces803D（二分+贪心，第一次写博客）

Magazine Ad

The main city magazine offers its readers an opportunity to publish their ads. The format of the ad should be like this:

There are space-separated non-empty words of lowercase and uppercase Latin letters.

There are hyphen characters '-' in some words, their positions set word wrapping points. Word can include more than one hyphen.

It is guaranteed that there are no adjacent spaces and no adjacent hyphens. No hyphen is adjacent to space. There are no spaces and no hyphens before the first word and after the last word.

When the word is wrapped, the part of the word before hyphen and the hyphen itself stay on current line and the next part of the word is put on the next line. You can also put line break between two words, in that case the space stays on current line. Check notes for better understanding.

The ad can occupy no more that k lines and should have minimal width. The width of the ad is the maximal length of string (letters, spaces and hyphens are counted) in it.

You should write a program that will find minimal width of the ad.

Input

The first line contains number k (1 ≤ k ≤ 10⁵).

The second line contains the text of the ad — non-empty space-separated words of lowercase and uppercase Latin letters and hyphens. Total length of the ad don't exceed 10⁶ characters.

Output

Output minimal width of the ad.

Examples

Input

4
garage for sa-le

Output

Input

4
Edu-ca-tion-al Ro-unds are so fun

Output

Note

Here all spaces are replaced with dots.

In the first example one of possible results after all word wraps looks like this:


garage.
for.
sa-
le

The second example:


Edu-ca-
tion-al.
Ro-unds.
are.so.fun

题目大意：有一组字符串，用连字符‘-’以及空格‘ ’进行分割，要求分割不超过k段，求分割后的最小宽度（宽度就是分割后最长的字符串的长度）。
思路：博主是个菜鸡，一开始没啥思路，学姐讲题的时候才想到用二分。。。。。。。。
　　经过不断地啃博客（正经脸），算是明白一点如何从 二分 入手这道题。
　　把每一段字符串 按照一个长度 x 进行分割，得到的字符串长度不能超过 x ，看最后得到的行数是否小于k；
　　如果按长度x进行分割得到的行数小于k 那么按长度 x+1 进行分割所得到的行数必定小于k。
　　注意 最小宽度 定义，这个时候我们就可以用二分，不断地去逼近这个最小宽度，就可以得到答案。
　　最后注意的就是二分的上下界，上界就是初始字符串的长度s.size(),下界可以是s.size()/k（这个博主就不解释了）。
AC代码：

 1 #include
 2 using namespace std;
 3 vector<int>v;
 4 string s;
 5 int k;
 6 bool check(int x){
 7     int line = 0;// 记录以x切割时可以得到的行数     
 8     int len = 0; 
 9     for(int i = 0 ;  i ){
10         if(v[i] > x){
11             return 0;// 如果v[i] > x 说明存在v[i]让x无法表示（说明x取小了） 
12         }
13         if(v[i] + len > x){
14             line++;
15             len = v[i];
16         }else if(v[i] + len == x){
17             line++;
18             len = 0;
19         }else if(v[i] + len < x){
20             len += v[i];
21         }// 将字符串 以不大于x 的长度分割
22         // line 记录进行分割后得到的总行数 
23     }
24     if(len > 0) line++;// 注意分割最后的一小段字符串是否忽略 
25     return line <= k;// 根据x分割所得到的总行数不能大于k 
26 }
27 
28 int main(){
29     while(~scanf("%d",&k)){
30         v.clear();
31         getchar();
32         getline(cin,s);
33         int j = 0;
34         for(int i = 0 ; i ){
35             if(s[i] == ' ' || s[i] == '-'){
36                 v.push_back(j + 1);
37                 j = 0;
38             }else j++;
39         }
40         v.push_back(j);// 不要忘记末尾的字符串长度 
41         int l = s.size()/k, r = s.size();
42         while(r - l > 0){
43             int mid = (r + l)/ 2;
44             if(check(mid)){
45                 r = mid;
46             }else{
47                 l = mid + 1;
48             }
49         }
50         printf("%d\n",l);
51     }
52     return 0;
53 }