Задана строка T, рассмотрим некоторую ее подстроку S. Определим функцию f(S):

f(S) = |S| ✕ (КОЛИЧЕСТВО ВХОЖДЕНИЙ S В T)

Ваша задача — посчитать, какое максимальное значение принимает f(S) на множестве всех подстрок строки T.

В единственной строке записана строка T, состоящая только из строчных букв латинского алфавита.

Выведите целое число — ответ на задачу.

• 1 ≤ |T| ≤ 10⁵

aaaaaa

12

f('a') = 6
f('aa') = 10
f('aaa') = 12
f('aaaa') = 12
f('aaaaa') = 10
f('aaaaaa') = 6

abcabcddd

9

f("a") = 2
f("b") = 2
f("c") = 2
f("ab") = 4
f("bc") = 4
f("ddd") = 3
f("abc") = 6
f("abcabcddd") = 9