Иван хочет написать письмо своему другу. Письмо — строка s, состоящая из строчных латинских букв.
К сожалению, как только Иван начал писать письмо, он понял, что оно слишком длинное, и писать его целиком придётся очень долго. Поэтому он хочет написать сжатую версию строки s вместо самой строки.
Сжатая версия строки s — последовательность строк c1, s1, c2, s2, ..., ck, sk, где ci — десятичная запись числа ai (без лидирующих нулей), а si — некоторая строка из строчных латинских букв. Если Иван запишет строку s1 ровно a1 раз, потом s2 ровно a2 раз, и так далее, у него получится строка s.
Длина сжатой версии равна |c1| + |s1| + |c2| + |s2|... |ck| + |sk|. Среди всех сжатых версий Иван хочет выбрать такую, что её длина минимальна. Помогите Ивану определить минимально возможную длину.
Примечание
В первом примере Иван выберет следующую версию: c1 — 10, s1 — a.
Во втором примере Иван выберет следующую версию: c1 — 1, s1 — abcab.
В третьем примере Иван выберет следующую версию: c1 — 2, s1 — c, c2 — 1, s2 — z, c3 — 4, s3 — ab.