Problem
Chloé veut écrire une lettre à son amie. Lettre - chaîne s, composée de lettres latines minuscules.
Malheureusement, dès que Chloé a commencé à écrire la lettre, elle s'est rendu compte qu'elle était trop longue et qu'il faudrait beaucoup de temps pour l'écrire dans son intégralité. Elle veut donc écrire une version compressée de la chaîne s au lieu de la chaîne elle-même.
Une version compressée de la chaîne s — la séquence de chaînes c
1, s
1, c
2, s
2, ..., c
k, s
k, où c
i — représentation décimale de a
i (sans zéros non significatifs) et s
i — une chaîne de lettres latines minuscules. Si Chloé écrit la chaîne s
1 exactement une
1 fois, alors s
2 exactement une
2 fois, et ainsi sur , il produira la chaîne s.
La longueur de la version compressée est |c
1| + |s
1| + |c
2| + |s
2|... |c
k| + |s
k|. Parmi toutes les versions compressées, Chloé veut choisir celle qui a la longueur la plus courte. Aidez Chloé à trouver la longueur la plus courte possible.
Saisie :
La ligne unique de l'entrée contient une chaîne s composée de lettres latines minuscules (1 ≤ |s| ≤ 5000).
Sortie :
Imprimer un seul entier — la longueur minimale de la version compressée de la chaîne s.
Exemples :
| Entrée |
Sortie |
| aaaaaaaaa |
3 |
| abcab |
6 |
| cczabababab |
7 |
Explications :
Dans le premier exemple, Chloé sélectionnera la version suivante : c
1 — 10, s
1 &mdash ; a.
Dans le deuxième exemple, Chloé sélectionnera la version suivante : c
1 — 1, s
1 &mdash ; abcab.
Dans le troisième exemple, Chloé choisira la version suivante : c
1 — 2, s
1 &mdash ; c, c
2 — 1, s
2 &mdash ; z, c
3 — 4, s
3 &mdash ; ab.