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 occurrences of this substring in $s$ multiplied by its length.

For the given string $s$, find the maximum existence value among all palindromic substrings.

Input Format

One line, a non-empty string $s$ consisting of lowercase Latin letters (a~z).

Output Format

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

abacaba

7

www

4

Hint

Sample Explanation 1

Use $\lvert s \rvert$ to denote the length of 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 it reads the same from left to right and from right to left.

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

Therefore, the maximum existence value among 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$.

Translated by ChatGPT 5