主要城市杂志为其读者提供发布广告的机会。广告的格式应该是这样的:
存在由空格分隔的小写和大写拉丁字母的非空单词。
某些单词中有连字符“-”,它们的位置设置了换行点。单词可以包含多个连字符。
保证没有相邻的空格,也没有相邻的连字符。没有连字符与空格相邻。第一个单词之前和最后一个单词之后没有空格,也没有连字符。
当单词换行时,单词连字符之前的部分和连字符本身保留在当前行,单词的下一部分放在下一行。您还可以在两个单词之间放置换行符,在这种情况下,空格保留在当前行。检查注释以更好地理解。
广告占用的行数不能超过 k 行,并且宽度应最小。广告的宽度是其中字符串的最大长度(字母、空格和连字符都计算在内)。
您应该编写一个程序来找到广告的最小宽度。
输入
第一行包含数字 k (1 ≤ k ≤ 105)。
第二行包含广告文本 — 由小写和大写拉丁字母和连字符组成的非空空格分隔单词。广告的总长度不超过 106 个字符。
输出
输出广告的最小宽度。
示例
输入 #1
4 garage for sa-le
输出 #1
7
输入 #2
4 Edu-ca-tion-al Ro-unds are so fun
输出 #2
10
注意
此处所有空格均替换为点。
在第一个示例中,所有自动换行后的可能结果如下所示:
第二个例子: