Problem
Chloe quiere escribir una carta a su amiga. Letra - cadena s, que consiste en letras latinas minúsculas.
Desafortunadamente, tan pronto como Chloe comenzó a escribir la carta, se dio cuenta de que era demasiado larga y que le llevaría mucho tiempo escribirla en su totalidad. Así que quiere escribir una versión comprimida de la cadena s en lugar de la cadena misma.
Una versión comprimida de la cadena s — la secuencia de cadenas c
1, s
1, c
2, s
2, ..., c
k, s
k, donde c
i — representación decimal de a
i (sin ceros a la izquierda) y s
i — alguna cadena de letras latinas minúsculas. Si Chloe escribe la cadena s
1 exactamente
1 veces, entonces s
2 exactamente
2 veces, y así on , producirá la cadena s.
La longitud de la versión comprimida es |c
1| + |s
1| + |c
2| + |s
2|... |c
k| + |s
k|. Entre todas las versiones comprimidas, Chloe quiere elegir la que tiene la longitud más corta. Ayuda a Chloe a encontrar la longitud más corta posible.
Entrada:
La única línea de la entrada contiene una cadena s que consta de letras latinas en minúsculas (1 ≤ |s| ≤ 5000).
Salida:
Imprime un solo entero — la longitud mínima de la versión comprimida de la cadena s.
Ejemplos:
| Entrada |
Salida |
| aaaaaaaaaa |
3 |
| abcab |
6 |
| cczabababab |
7 |
Explicaciones:
En el primer ejemplo, Chloe seleccionará la siguiente versión: c1 — 10, s1 — a.
En el segundo ejemplo, Chloe elegirá la siguiente versión: c1 — 1, s1 — abcab.
En el tercer ejemplo, Chloe elegirá la siguiente versión: c1 — 2, s1 — c, c2 — 1, s2 — z, c3 — 4, s3 — ab.