APIO14_A - Palindromes

You are given a string of lower-case Latin letters. Let us define substring’s “occurrence value” as the number of the substring occurrences in the string multiplied by the length of the substring. For a given string find the largest occurrence value of palindromic substrings.

Input

The only line of input contains a non-empty string S of lower-case Latin letters (a-z), |S| <= 300,000.

Output

Output one integer – the largest occurrence value of palindromic substrings.

Example

Input:
abacaba

Output:
7

Added by:Se7s
Date:2014-09-25
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:APIO 2014

hide comments
2016-06-11 19:35:11
what is the ans of this case
abbbkkui
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.