| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 63 | 34 | 22 | 45.833% |
Однажды в одном далеком-далеком городе БайтСити компания МакроХард решила разместить по всему городу свои рекламные плакаты. Для этих плакатов было заготовлено несколько рекламных лозунгов.
Каждый лозунг состоит из нескольких слов, порядок которых, разумеется, менять нельзя. Каждое следующее слово можно расположить на плакате или в новой строке горизонтально, или, начиная со следующей строки, вертикально по одной букве слова в одной строке. При этом нельзя два последовательных слова написать вертикально, так как в этом случае их нельзя будет различить.
Известно, что рекламный плакат можно сделать сколь угодно высоким, но, к сожалению, ширина плаката ограничена. Поэтому компания МакроХард хочет разместить лозунг на плакате таким образом, чтобы минимизировать максимальную ширину. Каждое слово печатается одним и тем же моноширинным шрифтом, потому достаточно минимизировать длину самого длинного слова, записанного горизонтально.
В данной задаче Вам дан один рекламный лозунг. Необходимо найти размещение, минимизирующее ширину плаката.
В первой строке входного файла задано одно число $n$ (1ドル \le n \le 100$) --- число слов в рекламном лозунге. В следующих $n$ строках записан сам лозунг --- по одному слову в строке.
Длина каждого слова не менее двух и не более 100 символов. Слова состоят только из строчных латинских букв.
В выходной файл выведите единственное число --- минимальную ширину плаката.
5 THIS IS AN EASY EXAMPLE
4
9 AND THIS IS SECOND SAMPLE FOR THIS EASY PROBLEM
6