Migrated from Lutece 2819 回文串

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

对于一个串 $s$，定义 $s$ 的某个子串的权值为其在原串的出现次数乘以该子串的长度。

给定串 $s$， 求其所有回文子串的最大权值。

Input

一行，一个由小写字母组成的非空串 $s$。

Output

一行一个整数，表示给定串的所有回文子串的最大权值。

Samples

abacaba

7

www

4

Constraints

$1 \le |s| \le 10^6$.

Resources

2022 UESTC ICPC Training for String and Search Algorithm