Module: Padrões em Programação Dinâmica

Problem

Chloe quer escrever uma carta para sua amiga. Letra - string s, consistindo em letras latinas minúsculas.
Infelizmente, assim que Chloe começou a escrever a carta, ela percebeu que era muito longa, e levaria muito tempo para escrevê-la inteira. Então ela quer escrever uma versão comprimida da string s ao invés da própria string.

Uma versão compactada da string s — a sequência de strings c₁, s₁, c₂, s₂,   ..., c_k, s_k, onde c_i — representação decimal de a_i (sem zeros à esquerda) e s_i — alguma sequência de letras latinas minúsculas. Se Chloe escrever a string s₁ exatamente ₁ vezes, então s₂ exatamente ₂ vezes, e assim on , produzirá a string s.
O comprimento da versão comprimida é |c₁| + |s₁| + |c₂|  +  |s₂|... |c_k| + |s_k|. Entre todas as versões comprimidas, Chloe deseja escolher aquela com o menor comprimento. Ajude Chloe a encontrar o menor comprimento possível.

Entrada:
A única linha da entrada contém uma string s que consiste em letras latinas minúsculas (1 ≤ |s| ≤ 5000).

Saída:
Imprima um único inteiro — o comprimento mínimo da versão comprimida da string s.

Exemplos:
 

Entrada	Saída
aaaaaaaaa	3
abcab	6
cczabababab	7

Explicações:
No primeiro exemplo, Chloe selecionará a seguinte versão: c₁ — 10, s₁ — a.
No segundo exemplo, Chloe escolherá a seguinte versão: c₁ — 1, s₁ — abcab.
No terceiro exemplo, Chloe escolherá a seguinte versão: c₁ — 2, s₁ — c, c₂ — 1, s₂ — z, c₃ — 4, s₃ — ab.