题目描述

对于 $S$，记 $c_S(T)$ 表示 $T$ 在 $S$ 中的出现次数。对所有回文串 $T$，求 $\max_T(c_S(T) \cdot |T|^2)$。

输入格式

输入只有一行，包含一个字符串 $S$。

输出格式

输出一行一个整数，表示答案。

样例数据

样例 1 输入

hyddakioizjoi

样例 1 输出

9

样例 1 解释

取 $T=\mathsf{ioi}$。

样例 2 输入

hyakioivilavpnshadowsocksapioioihyakioiagain

样例 2 输出

36

样例 2 解释

取 $T=\mathsf{ioi}$。

子任务

对于所有数据，$|S| \leq 10^6$。

• Subtask 1(35 Points): $|S| \leq 3.5 \times 10^4$。
• Subtask 2(65 Points): 没有额外的限制。