Олимпиадный тренинг

Задача . Сжатие строки


Хлоя хочет написать письмо своей подруге. Письмо - строка s, состоящая из строчных латинских букв.
К сожалению, как только Хлоя начала писать письмо, она поняла, что оно слишком длинное, и писать его целиком придётся очень долго. Поэтому она хочет написать сжатую версию строки s вместо самой строки.

Сжатая версия строки s — последовательность строк c1, s1, c2, s2, ..., ck, sk, где ci — десятичная запись числа ai (без лидирующих нулей), а si — некоторая строка из строчных латинских букв. Если Хлоя запишет строку s1 ровно a1 раз, потом s2 ровно a2 раз, и так далее, у нее получится строка s.
Длина сжатой версии равна |c1| + |s1| + |c2| + |s2|... |ck| + |sk|. Среди всех сжатых версий Хлоя хочет выбрать такую, что её длина минимальна. Помогите Хлое определить минимально возможную длину.

Входные данные:
В единственной строке входных данных записана строка s, состоящая из строчных латинских букв (1 ≤ |s| ≤ 5000).

Выходные данные:
Выведите одно целое число — минимальную длину сжатой версии строки s.

Примеры:
 
Входные данные Выходные данные
aaaaaaaaaa 3
abcab 6
cczabababab 7


Пояснения:
В первом примере Хлоя выберет следующую версию: c1 — 10, s1 — a.
Во втором примере Хлоя выберет следующую версию: c1 — 1, s1 — abcab.
В третьем примере Хлоя выберет следующую версию: c1 — 2, s1 — c, c2 — 1, s2 — z, c3 — 4, s3 — ab.
 

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w641
Комментарий учителя