Module: Pattern nella programmazione dinamica

Problem

Chloe vuole scrivere una lettera alla sua amica. Lettera - stringa s, composta da lettere latine minuscole.
Sfortunatamente, non appena Chloe ha iniziato a scrivere la lettera, si è resa conto che era troppo lunga e che ci sarebbe voluto molto tempo per scriverla nella sua interezza. Quindi vuole scrivere una versione compressa della stringa s invece della stringa stessa.

Una versione compressa della stringa s — la sequenza di stringhe c₁, s₁, c₂, s₂,  ..., c_k, s_k, dove c_i — rappresentazione decimale di a_i (senza zeri iniziali) e s_i — qualche stringa di lettere latine minuscole. Se Chloe scrive la stringa s₁ esattamente una₁ volte, allora s₂ esattamente una₂ volte, e così on , produrrà la stringa s.
La lunghezza della versione compressa è |c₁| + |s₁| + |c₂|  +  |s₂|... |c_k| + |s_k|. Tra tutte le versioni compresse, Chloe vuole scegliere quella con la lunghezza minore. Aiuta Chloe a trovare la lunghezza più breve possibile.

Inserimento:
La singola riga dell'input contiene una stringa s costituita da lettere latine minuscole (1 ≤ |s| ≤ 5000).

Uscita:
Stampa un singolo numero intero — la lunghezza minima della versione compressa della stringa s.

Esempi:
 

Input	Uscita
aaaaaaaaaa	3
abcab	6
cczabababab	7

Spiegazioni:
Nel primo esempio, Chloe selezionerà la seguente versione: c₁ — 10, s₁ — a.
Nel secondo esempio, Chloe selezionerà la seguente versione: c₁ — 1, s₁ — abcab.
Nel terzo esempio, Chloe sceglierà la seguente versione: c₁ — 2, s₁ — c, c₂ — 1, s₂ — z, c₃ — 4, s₃ — ab.