给你一个由小写拉丁字母组成的字符串 $s$。我们定义 $s$ 的一个子串的存在值为这个子串在 $s$ 中出现的次数乘以这个子串的长度。

对于给你的这个字符串 $s$，求所有回文子串中的最大存在值。

输入格式

一行，一个由小写拉丁字母（a~z）组成的非空字符串 $s$。

输出格式

输出一个整数，表示所有回文子串中的最大存在值。

样例一

input

abacaba

output

7

explanation

用 $|s|$ 表示字符串 $s$ 的长度。

一个字符串 $s_1{s}_2\dots s_{|s|}$ 的子串是一个非空字符串 $s_i{s}_{i+1}\dots s_j$，其中 $1\le i\le j\le |s|$。每个字符串都是自己的子串。

一个字符串被称作回文串当且仅当这个字符串从左往右读和从右往左读都是相同的。

这个样例中，有 $7$ 个回文子串 a，b，c，aba，aca，bacab，abacaba。他们的存在值分别为 $4,2,1,6,3,5,7$。

所以回文子串中最大的存在值为 $7$。

样例二

input

www

output

4

限制与约定

第一个子任务共 8 分，满足 $1\le |s|\le 100$。

第二个子任务共 15 分，满足 $1\le |s|\le 1000$。

第三个子任务共 24 分，满足 $1\le |s|\le 10000$。

第四个子任务共 26 分，满足 $1\le |s|\le 100000$。

第五个子任务共 27 分，满足 $1\le |s|\le 300000$。

时间限制：$1\mathtt{\text{s}}$

空间限制：$256\mathtt{\text{MB}}$

下载

样例数据下载