Module: Patterns in Dynamic Programming


Problem

4 /7


String compression

Problem

Chloe wants to write a letter to her friend. Letter - string s, consisting of lowercase Latin letters.
Unfortunately, as soon as Chloe started writing the letter, she realized that it was too long, and it would take a very long time to write it in its entirety. So she wants to write a compressed version of the string s instead of the string itself.

A compressed version of the string s — the sequence of strings c1, s1, c2, s2,  ..., ck, sk, where ci — decimal representation of ai (without leading zeros), and si — some string of lowercase Latin letters. If Chloe writes the string s1 exactly a1 times, then s2 exactly a2 times, and so on , it will produce the string s.
The length of the compressed version is |c1| + |s1| + |c2| +  |s2|... |ck| + |sk|. Among all the compressed versions, Chloe wants to choose the one with the shortest length. Help Chloe find the shortest possible length.

Input:
The single line of the input contains a string s consisting of lowercase Latin letters (1 ≤ |s| ≤ 5000).

Output:
Print a single integer — the minimum length of the compressed version of the string s.

Examples:
 
Input Output
aaaaaaaaaa 3
abcab 6
cczabababab 7


Explanations:
In the first example, Chloe will select the following version: c1 — 10, s1 — a.
In the second example, Chloe will choose the following version: c1 — 1, s1 — abcab.
In the third example, Chloe will choose the following version: c1 — 2, s1 — c, c2 — 1, s2 — z, c3 — 4, s3 — ab.