시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB236523.810%

문제

A palindrome is a word that reads the same backwards as forwards. For example, “a”, “abba” and “anavolimilovana” are palindromes A sample is a string of one or more lower case letters of the English alphabet, and the weight of a sample is the number of its substrings (words) that are palindromes, counting each word occurrence separately.

More precisely, let w be a sample of length n. The word wa,b is obtained by taking all characters from position a to position b in sample w. The weight of sample w is defined as the number of different pairs of integers a, b (1 ≤ abn) such that the word wa,b is a palindrome.

You are given the sample w. It can either be left unchanged, or exactly one position can be chosen and the letter on that position arbitrarily changed. Find the maximal possible sample weight that can be obtained as described above.

입력

The first line of input contains the given sample w – a string of lower case letters of the English alphabet.

출력

You must output the required maximal possible weight.

서브태스크

번호 배점 제한
1 17

1 ≤ n ≤ 100

2 37

101 ≤ n ≤ 5 000

3 46

5001 ≤ n ≤ 100 000

예제 입력 1

aaaa

예제 출력 1

10

예제 입력 2

baccb

예제 출력 2

9

예제 입력 3

slavko

예제 출력 3

7

힌트

Clarification of the first example: Each substring from the sample already is a palindrome, so it is best left unchanged.

Clarification of the second example: If we change the second letter of the sample to “c”, we will get the sample “bcccb” with a weight of 9.

채점 및 기타 정보

  • 예제는 채점하지 않는다.