꺾은선

Basia는 문자열 $s$를 가지고 있고, 각 문자는 영어 알파벳 소문자 중 처음 16개 중 하나이다.

이 문자열의 각 문자는 오른쪽 또는 위쪽 화살표로 바뀌는데, 같은 문자는 반드시 같은 화살표로 바뀌어야 한다. 예를 들어 문자열 "banan"은 $\uparrow \uparrow \rightarrow \uparrow \rightarrow$ 또는 $\uparrow \uparrow \uparrow \uparrow \uparrow$로 바뀔 수 있지만, $\rightarrow \rightarrow \rightarrow \uparrow \rightarrow$는 얻을 수 없다. 두 개의 문자 'a'를 서로 다른 화살표로 바꿔야 하기 때문이다.

Basia는 이렇게 얻은 화살표 열로 꺾은선을 그린다. 연필을 점 $(0, 0)$에 놓고 시작해서, $n$번 연필을 다음 화살표 방향으로 오른쪽 또는 위쪽으로 1만큼 움직인다.

이 그림의 결과는 꺾은선과 OX축 사이의 넓이로 정의한다. 엄밀히 말해 이 넓이는 $y \geq 0$이고, 꺾은선에 속하는 어떤 점 $(x, y')$가 $y' \geq y$를 만족하는 점 $(x, y)$ 전체의 집합이다.

Basia의 그림 결과로 얻을 수 있는 최댓값은 얼마인가?

표준 입력의 첫 번째 줄이자 유일한 줄에 문자열 $s$ ($1 \leq |s| \leq 300\,000$)가 주어진다. $s$는 영어 알파벳 소문자 'a'-'p' (16개 문자)로 이루어진다.

문자를 주어진 규칙에 따라 화살표로 바꿨을 때 얻을 수 있는 그림 결과의 최댓값을 정수 하나로 출력한다.

문자열 "banan"은 $\uparrow \uparrow \rightarrow \uparrow \rightarrow$로 바꾸는 것이 좋다. 이때 꺾은선 아래의 넓이는 $5$이다:

문자열 "abcdefghijklmnopaaaa"에는 넓이가 90인 최적해가 두 가지 있다: