← 返回题目列表

Codeforces · 803/D

D. 杂志广告

中文机器翻译题面 查看原题

主要城市杂志为其读者提供发布广告的机会。广告的格式应该是这样的:

存在由空格分隔的小写和大写拉丁字母的非空单词。

某些单词中有连字符“-”,它们的位置设置了换行点。单词可以包含多个连字符。

保证没有相邻的空格,也没有相邻的连字符。没有连字符与空格相邻。第一个单词之前和最后一个单词之后没有空格,也没有连字符。

当单词换行时,单词连字符之前的部分和连字符本身保留在当前行,单词的下一部分放在下一行。您还可以在两个单词之间放置换行符,在这种情况下,空格保留在当前行。检查注释以更好地理解。

广告占用的行数不能超过 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

注意

此处所有空格均替换为点。

在第一个示例中,所有自动换行后的可能结果如下所示:

第二个例子: