회문 Batch 컴파일 명령

영문 소문자로 구성된 문자열(string)이 주어져 있다. 이 문자열의 부문자열(substring)들에 대해서 "점수"를 정의하는데, 점수는 부문자열의 길이에 그 부문자열이 전제 문자열에 등장하는 횟수를 곱한 값이다. 주어진 문자열에 대해 회문(palindrome)이 되는 부문자열들 중 가장 높은 점수를 가진 것을 찾아서 그 점수를 출력하는 프로그램을 작성하라.

입력

입력은 단 한 줄이며, 영문 소문자(a-z)로 구성된 문자열이 주어진다.

출력

출력은 하나의 자연수이며 회문이 되는 부문자열들에서 찾을 수 있는 가장 높은 점수이다.

예제

예제 1

입력

abacaba

출력

7

예제 2

입력

wow

출력

4

추가 설명

문자열 $s$에 대해서 $|s|$는 그 길이를 말한다.

부문자열은 문자열 $s_{1}, s_{2}, \cdots, s_{|s|}$의 임의의 연속적인 일부분, 즉 $s_{i}s_{i+1}\cdots s_{j}$ ($1 \le i \le j \le |s|$)이다. 문자열 전체도 자신의 부문자열이다.

어떤 문자열이 회문이라 함은 그 문자열을 앞에서 뒤로 읽으나 뒤에서 앞으로 읽으나 동일한 경우를 말한다.

입출력 예의 첫 번째 경우의 문자열에 회문이 되는 부문자열은 모두 일곱 가지이다: a, b, c, aba, aca, bacab, abacaba.

• a는 문자열에 네 번 등장하므로 점수는 $4 \times 1 = 4$점이다.
• b는 문자열에 두 번 등장하므로 점수는 $2 \times 1 = 2$점이다.
• c는 문자열에 한 번 등장하므로 점수는 $1 \times 1 = 1$점이다.
• aba는 문자열에 두 번 등장하므로 점수는 $3 \times 2 = 6$점이다.
• aca는 문자열에 한 번 등장하므로 점수는 $3 \times 1 = 3$점이다.
• bacab는 문자열에 한 번 등장하므로 점수는 $5 \times 1 = 5$점이다.
• abacaba는 문자열에 한 번 등장하므로 점수는 $7 \times 1 = 7$점이다.

따라서, 회문들 중 가장 높은 점수는 7점이다.

채점

다음과 같은 다섯 개의 서브태스크로 채점이 이루어 진다.

1. (8점) $1 \le |s| \le 100$
2. (15점) $1 \le |s| \le 1000$
3. (24점) $1 \le |s| \le 10000$
4. (26점) $1 \le |s| \le 100000$
5. (27점) $1 \le |s| \le 300000$