광고 포스터

BayteCity라는 먼 도시에서 MacroHard 회사가 도시 곳곳에 광고 포스터를 붙이기로 했다. 회사는 이 포스터에 쓸 광고 문구를 여러 개 준비했다.

각 문구는 여러 단어로 이루어져 있으며, 단어의 순서는 바꿀 수 없다. 다음 단어는 새 줄에 가로로 쓰거나, 다음 줄부터 세로로 쓸 수 있다. 세로로 쓰는 경우 한 줄에 단어의 글자를 하나씩 쓴다. 연속된 두 단어를 모두 세로로 쓸 수는 없다. 그러면 두 단어를 구별할 수 없기 때문이다.

포스터는 필요한 만큼 길게 만들 수 있지만 너비에는 제한이 있다. MacroHard는 포스터의 최대 너비가 최소가 되도록 문구를 배치하려고 한다. 모든 단어는 같은 고정폭 글꼴로 인쇄되므로, 가로로 쓰인 단어 중 가장 긴 단어의 길이만 최소로 하면 된다.

문구 하나가 주어진다. 포스터의 너비를 최소로 하는 배치를 구하라.

첫 줄에 정수 $n$ ($1 \le n \le 100$)이 주어진다. 이는 광고 문구에 들어 있는 단어의 개수이다. 이어서 $n$개의 줄에 한 줄에 하나씩 단어가 주어진다.

각 단어의 길이는 2 이상 100 이하이며, 소문자 라틴 알파벳으로만 이루어져 있다.

포스터의 최소 너비를 정수 하나로 출력한다.