한국디지털미디어고등학교는 너무 길다

디미고의 공식 명칭인 한국디지털미디어고등학교는 너무 길다. 그래서 학생회는 이 학교를 문과 계열 학교와 이과 계열 학교 둘로 나누어 이름을 줄이려 한다. 문과 계열 학교에는 디지털콘텐츠과와 이비지니스과가 속하고, 이과 계열 학교에는 웹프로그래밍과와 해킹방어과가 속한다. 학생회는 나눈 두 학교의 이름을 새로 지어야 한다.

학생회는 정체성을 지키기 위해 원래 학교 이름을 연속된 앞부분과 나머지 뒷부분으로 나누기로 했다. 예를 들어 KoreaDigitalMediaHighSchool은 앞부분 KoreaDigital과 뒷부분 MediaHighSchool로 나눌 수 있다. 앞부분이나 뒷부분은 빈 문자열이어도 된다.

두 계열은 서로 라이벌 의식을 가지고 있으므로, 학생회는 나눈 두 이름이 최대한 달랐으면 한다. 이를 객관적으로 판단하기 위해 불일치도라는 값을 사용한다. 학교 이름을 나눈 두 문자열을 각각 A, B라고 하면 불일치도는 $\mathrm{min}(|A|, |B|) - \mathrm{LCS}(A, B)$이다. 문자열 S에 대해 $|S|$는 S의 길이이고, $\mathrm{min}(x, y)$는 x와 y 중 크지 않은 수이다.

LCS(A, B)는 대소문자를 구분하여 A와 B 모두의 부분 문자열이 되는 문자열 중 가장 긴 문자열의 길이이다. 예를 들어 ABCD와 ABDF의 공통 부분 문자열 중 가장 긴 것은 ABD이므로 LCS는 3이다. 부분 문자열은 원래 문자열에서 순서를 유지하면서 0개 이상의 문자를 제거해 만든 문자열이다. 예를 들어 ABC와 BD는 ABCD의 부분 문자열이지만 BDC, EAB, abc는 아니다.

한국디지털미디어고등학교를 잘 나눌 수 있도록 가능한 불일치도의 최댓값을 구하자.

첫 번째 줄에 학교 이름을 나타내는 문자열 $S$가 주어진다. $S$는 알파벳 소문자와 대문자로만 이루어져 있다. $(1 \leq |S| \leq 3\,000)$

첫 번째 줄에 불일치도의 최댓값을 출력한다.