Problem
クロエは友達に手紙を書きたいと思っています。 Letter - 小文字のラテン文字で構成される文字列 s。
残念なことに、クロエが手紙を書き始めるとすぐに、彼女はそれが長すぎることに気付きました。そこで彼女は、文字列そのものではなく、文字列 s の圧縮バージョンを書きたいと考えています。
文字列 s — の圧縮バージョン。文字列のシーケンス c
1, s
1, c
2, s
2, ..., c
k, s
k, ここで c
i — a
i の 10 進数表現 (先行ゼロなし)、および s
i —小文字のラテン文字の文字列。 Chloe が文字列 s
1 を正確に a
1 回書き込む場合、s
2 は正確に a
2 回、ということになります。の場合、文字列 s が生成されます。
圧縮バージョンの長さは |c
1| + |s
1| + |c
2| です。 + |s
2|... |c
k| + |s
k|.圧縮されたすべてのバージョンの中で、クロエは、長さが最も短いバージョンを選択したいと考えています。クロエができるだけ短い長さを見つけるのを手伝ってください。
入力:
入力の 1 行には、小文字のラテン文字 (1 ≤ |s| ≤ 5000) で構成される文字列 s が含まれています。
出力:
単一の整数を出力します —文字列 s の圧縮バージョンの最小長。
例:
<本体>
| 入力 |
出力 |
| あああああああ |
3 |
| abcab |
6 |
| cczabababab |
7 |
説明:
最初の例では、Chloe は次のバージョンを選択します: c1 — 10, s1 — a.
2 番目の例では、Chloe は次のバージョンを選択します: c1 — 1, s1 —
3 番目の例では、Chloe は次のバージョンを選択します: c1 — 2, s1 — c, c2 — 1, s2 — z, c3 — 4, s3 — a.