활자 사이의 강

조판에서 "강"은 단어 사이의 빈칸이 여러 줄에 걸쳐 이어지면서 아래로 흘러가는 공백의 열이다. 그림 1은 강을 빨간색으로 표시한 예다. 강이 잘 보이도록 글자는 일부러 흐리게 처리했다.

그림 1: 조판된 글에 나타난 강의 예.

강을 연구하는 Flo Ng는 세계의 강을 다룬 새 책에 가능한 한 긴 활자의 강을 넣으려고 한다. 본문은 고정폭 글꼴로 짜고(모든 글자와 공백의 너비가 같다), 폭이 정해진 왼쪽 정렬 단에 배치하며, 한 줄 안에서 단어 사이는 정확히 공백 한 칸으로 띄운다. 오른쪽 끝은 맞추지 않는다. Flo가 말하는 "강"은 연속한 줄에서 한 칸씩 고른 공백의 열로, 첫 공백을 뺀 각 공백의 위치가 바로 윗줄에서 고른 공백의 위치와 최대 1만큼만 차이 나야 한다. 줄 끝에 남는 공백은 강에 넣을 수 없다. 단어는 각 줄에 최대한 빽빽하게 채우고, 한 단어를 두 줄에 나누어 쓰지 않는다. 사용하는 줄 폭은 가장 긴 단어의 길이 이상이어야 한다. 그림 2는 같은 글을 서로 다른 두 줄 폭으로 짠 결과다.

그림 2: 두 가지 줄 폭에서 가장 긴 강(*).

글이 주어질 때, 그 글에서 가장 긴 공백의 강이 만들어지는 줄 폭을 구하라.

첫 줄에 글에 들어 있는 단어의 개수 $n$이 주어진다 ($2 \le n \le 2500$). 다음 줄부터 글의 단어가 주어진다. 각 단어는 영문 대문자와 소문자로만 이루어지고, 같은 줄에 있는 단어는 공백 한 칸으로 구분된다. 길이가 80을 넘는 단어는 없다.

가장 긴 강이 만들어지는 줄 폭과 그 강의 길이(강을 이루는 공백의 개수)를 한 줄에 공백 한 칸으로 구분해 출력한다. 같은 최댓값을 주는 줄 폭이 여러 개면 그중 가장 작은 값을 출력한다.