32189번 - '한국디지털미디어고등학교'는 너무 길다.

문제

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

학생회는 한국디지털미디어고등학교의 정체성을 지키기 위해 두 학교의 이름을 원래 학교 이름의 연속된 앞부분과 나머지 뒷부분으로 나누어 정하기로 했다. 예를 들어 "KoreaDigitalMediaHighSchool"을 앞부분 "KoreaDigital"과 뒷부분 "MediaHighSchool"으로 나눌 수 있다. 또한 앞부분 또는 뒷부분이 빈 문자열이어도 된다.

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

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

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

입력

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

출력

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

제한

힌트