流程图是您考虑过的另一种压缩方法。CC BY-NC 2.5，作者 Randall Munroe，来自 xkcd.com

下周，你将举办两年一度的“不插电流行歌曲大会”（Biannual Acoustic Popsong Convention）。当然，这次大会还需要包含一个卡拉 OK 之夜，届时将演唱所有你最喜欢的经典不插电流行歌曲！为了给所有参会者留下深刻印象，你决定通过背下所有歌曲的歌词来做好准备。但有一个问题：这些歌词非常长，所以你没有足够的时间来背诵所有内容！然而，你注意到许多歌曲中都包含相当多的重复。这让你产生了一个想法：先对歌词进行压缩，然后只背诵压缩后的版本。

你将使用的压缩方案如下。设 $s$ 为待压缩的字符串。你选择歌词中恰好一个非空子串 $t$，并将 $s$ 中尽可能多的不重叠的 $t$ 替换为一个之前未在 $s$ 中出现过的新字符。将替换后的结果记为 $s'$。现在你只需要记住子串 $t$ 和压缩后的字符串 $s'$。你希望知道，如果以这种方式压缩歌词，这两个字符串的最小总长度是多少。

作为一个例子，考虑第一个样例。在这种情况下，你想压缩歌词 "nanananananananabatman"。如果你将子串 "na" 替换为字符 "X"，压缩后的字符串将变为 "XXXXXXXXbatman"。在这种情况下，子串和压缩后字符串的总长度为 $2 + 14 = 16$。然而，如果你选择替换子串 "nana"，则压缩后的字符串为 "XXXXbatman"，总长度为 $4 + 10 = 14$，这是最优的。

输入格式

输入包含：

• 一行，包含一个字符串 $s$（$1 \le |s| \le 5000$），表示待压缩的歌词。该字符串仅由英文小写字母（a-z）组成。

输出格式

输出被替换的子串与压缩后字符串的最小总长度。

样例

输入样例 1

nanananananananabatman

输出样例 1

14

输入样例 2

abcabd

输出样例 2

6

输入样例 3

nocompression

输出样例 3

14