Problem Description

You are given a string \( s \) consisting of lowercase Latin letters. We define the existence value of a substring of \( s \) as the number of times this substring appears in \( s \) multiplied by the length of the substring.

For the given string \( s \), find the maximum existence value among all palindromic substrings.

Input Format

A single line containing a non-empty string \( s \) consisting of lowercase Latin letters (a-z).

Output Format

Output a single integer representing the maximum existence value among all palindromic substrings.

Sample Input and Output

Sample Input #1

abacaba

Sample Output #1

7

Sample Input #2

www

Sample Output #2

4

Notes

Sample Explanation 1

Let \( \lvert s \rvert \) denote the length of the string \( s \).

A substring of a string \( s_1 s_2 \dots s_{\lvert s \rvert} \) is a non-empty string \( s_i s_{i+1} \dots s_j \) where \( 1 \leq i \leq j \leq \lvert s \rvert \). Every string is a substring of itself.

A string is called a palindrome if and only if the string reads the same forward and backward.

In this example, there are 7 palindromic substrings: a, b, c, aba, aca, bacab, abacaba. Their existence values are 4, 2, 1, 6, 3, 5, 7 respectively.

Thus, the maximum existence value among the palindromic substrings is 7.

Subtasks

• Subtask 1: 8 points, \( 1 \leq \lvert s \rvert \leq 100 \).
• Subtask 2: 15 points, \( 1 \leq \lvert s \rvert \leq 1000 \).
• Subtask 3: 24 points, \( 1 \leq \lvert s \rvert \leq 10000 \).
• Subtask 4: 26 points, \( 1 \leq \lvert s \rvert \leq 100000 \).
• Subtask 5: 27 points, \( 1 \leq \lvert s \rvert \leq 300000 \).

见题面 Input 部分

见题面 Output 部分