팝송

당신의 밴드 더 렝스-First Searchers는 새로운 노래를 작곡했다. 음악은 황홀하고 가사는 귀에 착 감기므로, 이 노래는 충분히 차트 선두에 오를 수 있다.

당신과 밴드가 스튜디오에 가서 노래를 녹음하기 전에 남은 일은 음악과 가사를 결합하는 것뿐이다. 노래는 인트로로 시작하고, 이어서 후렴이 나오며, 아웃트로로 끝나도록 이미 정했다(어차피 요즘은 아무도 절을 좋아하지 않는다). 노래의 각 부분에서 가사의 일부를 부르게 된다. 인트로와 아웃트로에서는 무엇이든 부를 수 있지만, 후렴에서는 한 번에 한 줄씩 더 정돈된 방식으로 불러야 한다. 음악과 리듬이 맞으려면 후렴의 모든 가사 줄은 또한 길이가 같아야 한다. 인트로와 아웃트로에서는 실제로 아무것도 부르지 않아도 되지만, 후렴은 적어도 두 줄로 이루어져야 한다.

가사의 어느 부분을 각 구간에 배정할지 선택하는 방법이 매우 많을 수 있으므로, 무작위로 하나를 고르는 대신 후렴의 운율값을 최대화하기로 한다. 운율값은 다음과 같이 정의한다. $N$을 후렴의 줄 수라 하고, $S$을 모든 줄이 공통으로 가지는 가장 긴 공통 접미사의 길이라고 하자. 그러면 운율값은 $N \cdot S$과 같다.

점수

당신의 풀이는 여러 테스트 케이스 그룹으로 채점된다. 한 그룹의 점수를 얻으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 배점 | 제한

$1$ |$30$| 문자열의 길이는 최대 $400$

$2$ |$30$| 문자열의 길이는 최대 $4\,000$

$3$ |$40$| 문자열의 길이는 최대 $15\,000$

입력의 첫 번째이자 유일한 줄에는 노래의 가사인 문자열이 주어진다. 문자열은 소문자(a-z)와 밑줄(```_`'')로만 이루어진다. 문자열의 길이는 $2$ 이상 $15\,000$ 이하이다.

달성할 수 있는 가장 큰 운율값을 나타내는 정수 하나를 출력한다.