你想要使用反向引用（backreference）来压缩一段给定的文本。反向引用是一对数字 $[a, b]$，表示接下来的 $b$ 个字符与当前位置之前 $a$ 个字符开始的 $b$ 个字符相同。这两个字符串可以重叠，即 $a$ 可以小于 $b$。

每个反向引用编码的代价为 3 个字节，无论该反向引用表示多少个字符。字符串中的每个字符编码代价为 1 个字节。

例如，字符串

abcabcabcabc

共有 12 个字符。但最后 9 个字符可以表示为对前 9 个字符的反向引用，如下所示：

abc[3,9]

该编码字符串的总代价为 6：字符串 abc 占用 3 个字节，反向引用占用 3 个字节。

输出编码该文本段的最小代价。

输入格式

输入包含单行字符串 $s$，满足 $1 \le |s| \le 10^5$。该行文本由大写字母（‘A’–‘Z’）、小写字母（‘a’–‘z’）和空格组成。行首和行尾不会有空格，且不会出现连续的空格。

输出格式

输出一个整数，表示使用反向引用表示输入字符串的最小代价。

样例

样例输入 1

abcabcabcabc

样例输出 1

6

样例输入 2

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

样例输出 2

4

样例输入 3

A man a plan a canal Panama

样例输出 3

25