附加文件

题目描述

有一些字符串很长，这样很占用存储空间，于是小明发明了一种新型字符串表示法，试图缩短字符串的长度。

他把连续的 K 个字符串 B 拼接形成的字符串用 K(B) 表示。当然，如果这样不能缩短字符串长度的话，也可以不用他的新型表示法。

例如：字符串 AAAAAABABABABCCC ，长度为 16。

采用小明的表示法，字符串可以表示为 6(A)3(BA)B3(C)，该新表示下的字符串长度为 14，比原字符串表示的长度缩小了。

当然，该字符串也可以表示为 5(A)4(AB)3(C)，此时长度为 13，长度更小了。

但我们发现其中的 CCC 长度为 3，新型表示为 3(C) 长度为 4，反而变大了。

所以更好的表示应该为 5(A)4(AB)CCC，长度为 12.

此外，还可以有多种表示。

我们把所有表示中（包含原始字符串），长度最短的那个表示，称为最好表示。

字符串 AAAAAABABABABCCC 的最好表示就是 5(A)4(AB)CCC，长度为 12.

现在给你一个字符串 S，请你求出最好表示的长度。

输入格式

一行，一个字符串 S，全部由英文大写字母构成。

输出格式

一个整数，表示 S 的最好表示的长度

样例输入1

AAAAAABABABABCCC

样例输出1

12

样例输入2

DINGDINGDANGDINGDINGDANGDINGDINGDANG

样例输出2

14

样例2解释

最好表示为 3(2(DING)DANG)

数据范围

100% 的数据：|S| ≤ 100