CF803D.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.

主流城市杂志为其读者提供发布广告的机会。广告的格式需满足以下要求：

• 广告由若干个非空单词组成，单词之间以空格分隔，单词仅包含小写和大写的拉丁字母；
• 某些单词中包含连字符 '-'，其位置指定了该单词的换行断点；一个单词中可包含多个连字符；
• 保证不存在相邻的空格，也不存在相邻的连字符；连字符不会与空格相邻；首词之前和末词之后均无空格或连字符。

当对单词进行换行时，连字符及其前面的部分保留在当前行，而连字符后面的部分则移至下一行。你也可以在两个单词之间插入换行符，此时空格保留在当前行。更多细节请参阅“注释”部分以加深理解。

广告最多占用 $k$ 行，且应具有最小可能的宽度。广告的宽度定义为其中所有行字符串长度（字符、空格和连字符均计入）的最大值。

你需要编写一个程序，求出广告的最小可能宽度。

The first line contains number k (1 ≤ k ≤ 105).

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 106 characters.

第一行包含一个数字 $k$（$1 \le k \le 10^5$）。

第二行包含广告文本——由小写和大写拉丁字母及连字符组成的、以空格分隔的非空单词。广告文本的总长度不超过 $10^6$ 个字符。

Output minimal width of the ad.

输出广告的最小宽度。

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

此处所有空格均被替换为英文句点（.）。

第一个示例中，全部换行后的可能结果之一如下所示：

garage.
for.
sa-
le

第二个示例：

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