题目描述

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

每个反向引用的编码成本固定为 3 字节，无论它代表多少个字符。字符串中的每个字符的编码成本为 1 字节。

例如，字符串

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

该编码后的总成本为 6：字符串 abc 占 3 字节，反向引用占 3 字节。

请输出对该文本段落进行编码的最小成本。

输入格式

输入只有一行，包含一个字符串 $s$，满足 $1 \le |s| \le 10^5$。该行文本由大写字母（'A'–'Z'）、小写字母（'a'–'z'）和空格组成。行的开头和结尾不会有空格，且不会出现两个空格相邻的情况。测试数据为 CRLF 格式。

输出格式

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

abcabcabcabc

6

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

4

A man a plan a canal Panama

25

提示

翻译由 DeepSeek V3.2 完成