CF803D Magazine Ad

本市的主流杂志为读者提供了发布广告的机会。广告的格式应如下所示： 广告内容由全部为小写和大写拉丁字母组成的非空单词构成，单词之间以空格分隔。 某些单词中可能包含连字符“-”，连字符的位置可以作为该单词的换行点。同时，一个单词中可以包含多个连字符。 保证不存在相邻的空格，也不存在相邻的连字符。没有连字符紧挨着空格。首单词前和末单词后均无空格和连字符。 当一个单词发生换行时，连字符之前的部分和连字符本身留在当前行，连字符后的部分移到下一行。你也可以在两个单词之间换行，这种情况下，空格留在当前行。具体用法见题目提示中的示例。 广告最多只能占用 $k$ 行，且需要使广告的宽度最小。广告的宽度定义为所有行中长度最大的字符串（其中字母、空格与连字符都计入长度）。 请你写程序求出广告的最小宽度。

第一行包含一个整数 $k$（$1 \leq k \leq 10^{5}$）。 第二行给出广告文本——由非空的小写和大写拉丁字母及连字符，以空格分隔的单词组成。广告文本总长度不超过 $10^6$ 个字符。

输出广告的最小宽度。

本题中所有空格已替换为点号。 在第一个示例中，将所有单词与连字符按照题目规定换行后，结果可能如下： `

garage.

for.

sa-

le

` 在第二个示例中： `

Edu-ca-

tion-al.

Ro-unds.

are.so.fun

` 由 ChatGPT 5 翻译