Maximum substring cost

No attempts yetTime limit2sMemory limit512 MB

Problem

You are given a string TT. For a string SS, let L(S)L(S) be the length of SS and let C(S)C(S) be the number of times SS occurs in TT. The cost of SS is

F(S)=L(S)×C(S)F(S) = L(S) \times C(S)

SS occurs in TT when SS appears as a substring of TT. Occurrences may overlap, and two occurrences with different starting positions count separately. For example, with TT = aaaaa and SS = aaa, the string SS occurs 3 times in TT, so F(S)=3×3=9F(S) = 3 \times 3 = 9.

Find the largest cost among all substrings of TT.

Input

The first line contains a string TT made up of lowercase letters. The length of TT is at least 1 and at most 100,000.

Output

Print, on one line, the maximum value of F(S)F(S) over all substrings SS of TT.