题目描述

给你一个长度为$\red{n}$的仅包含小写字母的字符串$\red{S ,}$定义$\red{Suffix_i}$表示$\red{S}$的以$\red{i}$为起始位置的后缀，然后定义$\red{w_{i,j}}$为$\red{Suffix_i}$和$\red{Suffix_j}$的$\red{LCP (}$最长公共前缀,例如"$\red{abca}$"和"$\red{abd}$"的$\red{LCP}$是 "$\red{ab}$"$\red{)}$。 现在想要让你把$\red{1,2,...,n}$这$\red{n}$个整数划分到两个非空集合$\red{T_1,T_2，}$对于一种划分的花费为:$\red{\sum_{i\in T_1}^{}{\sum_{j\in T_2}^{}{w_{i,j}}}}$

请问你能找到最小花费的划分吗？

输入格式

输入仅有一行，为字符串$\red{S}$

输出格式

输出一个整数表示最小花费

样例

输入样例1

aa

输出样例1

1

输入样例2

ab

输出样例2

0

提示

对于$\red{100\%}$的数据，$\red{2≤}$$\red{n≤}$$\red{00000}$