Palindrome

Time limit2sMemory limit128 MB

Summary

Find the palindromic substring that maximizes its length times its number of occurrences in the given string.

Level: Medium7 of 10
Topics: String matching, String
Solved: No attempts yet

Problem

You are given a string of lowercase letters. The appearance value of a substring is the number of times it occurs in the string multiplied by its length. Write a program that prints the largest appearance value among all palindrome substrings.

Input

The first line contains a string of lowercase letters (a-z). The length is at most 300,000.

Output

Print the largest appearance value among palindrome substrings on one line.

Hint

Let $|s|$ denote the length of string $s$ . A substring is a non-empty string $s_i s_{i+1} \ldots s_j$ with $1 \leq i \leq j \leq |s|$ . A palindrome reads the same from left to right and from right to left. A large appearance value can come from a short substring that appears many times or from a long palindrome that appears once.

Examples6

Example 1
Input
```
abacaba
```
Expected output
```
7
```
Example 2
Input
```
aaaaa
```
Expected output
```
9
```
Example 3
Input
```
a
```
Expected output
```
1
```
Example 4
Input
```
ab
```
Expected output
```
1
```
Example 5
Input
```
zz
```
Expected output
```
2
```
Example 6
Input
```
racecar
```
Expected output
```
7
```