노래방 압축

다음 주에 Biannual Acoustic Popsong Convention을 주최한다. 이 행사에는 좋아하는 어쿠스틱 팝송을 모두 함께 부르는 노래방 시간도 있어야 한다. 참석자들을 놀라게 하려고 모든 곡의 가사를 외우기로 했다. 그런데 가사가 너무 길어서 전부 외울 시간이 부족하다. 많은 곡에 반복되는 부분이 있으므로, 먼저 가사를 압축한 뒤 압축된 버전만 외우기로 했다.

압축 방법은 다음과 같다. 압축할 문자열을 $s$라고 하자. 가사에서 비어 있지 않은 부분 문자열 $t$를 정확히 하나 고른다. 그리고 $s$에 나타나는 $t$를 가능한 한 많이, $s$에 없던 새 문자 하나로 바꾼다. 이렇게 얻은 결과를 $s'$라고 한다. 이제 부분 문자열 $t$와 압축된 문자열 $s'$만 기억하면 된다. 이 방식으로 가사를 압축할 때, 두 문자열 길이의 합이 최소가 되는 값을 구하라.

예를 들어 가사 nanananananananabatman을 보자. 부분 문자열 na를 문자 X로 바꾸면 압축된 문자열은 XXXXXXXXbatman이 되고, 두 문자열 길이의 합은 $2 + 14 = 16$이다. 반면 nana를 바꾸면 압축된 문자열은 XXXXbatman이고 길이의 합은 $4 + 10 = 14$이며, 이것이 최적이다.

한 줄에 문자열 $s$ $(1 \leq |s| \leq 5000)$가 주어진다. 이는 압축할 가사다. 문자열은 영어 소문자(a-z)로만 이루어진다.

바꾼 부분 문자열과 압축된 문자열 길이의 합의 최솟값을 출력한다.