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_ ≤ 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.
## Output
Output minimal width of the ad.
[samples]
## 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
城市主要杂志为读者提供刊登广告的机会。广告的格式应如下所示：
由空格分隔的、由小写和大写拉丁字母组成的非空单词。
某些单词中包含连字符 _'-'_，其位置决定了单词换行的断点。一个单词可以包含多个连字符。
保证不存在相邻的空格，也不存在相邻的连字符。连字符不与空格相邻。第一个单词之前和最后一个单词之后没有空格和连字符。
当单词被换行时，连字符及其前面的部分保留在当前行，单词的剩余部分放到下一行。你也可以在两个单词之间换行，此时空格保留在当前行。详见注释以更好地理解。
广告最多只能占用 #cf_span[k] 行，且应具有最小宽度。广告的宽度定义为其中最长行的长度（计算字母、空格和连字符）。
你需要编写一个程序，求出广告的最小宽度。
第一行包含数字 #cf_span[k] (#cf_span[1 ≤ k ≤ 105])。
第二行包含广告文本——由空格分隔的、由小写和大写拉丁字母及连字符组成的非空单词。广告的总长度不超过 #cf_span[106] 个字符。
请输出广告的最小宽度。
以下所有空格均被替换为点号。
第一个例子中，所有单词换行后的一种可能结果如下：
第二个例子：
## Input
第一行包含数字 #cf_span[k] (#cf_span[1 ≤ k ≤ 105])。第二行包含广告文本——由空格分隔的、由小写和大写拉丁字母及连字符组成的非空单词。广告的总长度不超过 #cf_span[106] 个字符。
## Output
请输出广告的最小宽度。
[samples]
## Note
以下所有空格均被替换为点号。
第一个例子中，所有单词换行后的一种可能结果如下：
garage.for.sa-le
第二个例子：
Edu-ca-tion-al.Ro-unds.are.so.fun
**Definitions**
Let $ k \in \mathbb{Z} $ be the maximum number of lines allowed.
Let $ T $ be a string of length $ L \leq 10^6 $, consisting of space-separated words, where each word contains lowercase/uppercase Latin letters and hyphens ('-'), with no adjacent spaces, no adjacent hyphens, no hyphen-space adjacency, and no leading/trailing spaces or hyphens.
Let $ W = [w_1, w_2, \dots, w_m] $ be the sequence of words obtained by splitting $ T $ by spaces.
Each word $ w_i $ may contain zero or more hyphens, which define valid line break points within the word.
**Constraints**
1. $ 1 \leq k \leq 10^5 $
2. $ 1 \leq L \leq 10^6 $
3. Hyphens in a word define optional break points: a word $ w_i $ of length $ \ell $ with hyphens at positions $ p_1, p_2, \dots, p_h $ allows breaks after any prefix ending at $ p_j $ (i.e., after $ p_j $-th character, including the hyphen).
4. A line break may also occur between two words (at the space, which remains on the current line).
**Objective**
Find the minimal possible width $ W_{\min} $, defined as the maximum number of characters (letters, spaces, hyphens) in any single line, over all valid ways to break the text into at most $ k $ lines, respecting the break constraints.