Problem
Chloe ingin menulis surat kepada kawannya. Huruf - rentetan s, terdiri daripada huruf Latin huruf kecil.
Malangnya, sebaik sahaja Chloe mula menulis surat itu, dia menyedari bahawa surat itu terlalu panjang, dan ia akan mengambil masa yang sangat lama untuk menulisnya secara keseluruhan. Jadi dia mahu menulis versi mampat bagi rentetan s dan bukannya rentetan itu sendiri.
Versi mampat rentetan s — jujukan rentetan c
1, s
1, c
2, s
2, ..., c
k, s
k, di mana c
i — perwakilan perpuluhan a
i (tanpa sifar pendahuluan), dan s
i — beberapa rentetan huruf Latin huruf kecil. Jika Chloe menulis rentetan s
1 tepat a
1 kali, kemudian s
2 tepat satu
2 kali, dan seterusnya pada , ia akan menghasilkan rentetan s.
Panjang versi termampat ialah |c
1| + |s
1| + |c
2| + |s
2|... |c
k| + |s
k|. Di antara semua versi termampat, Chloe ingin memilih yang mempunyai panjang terpendek. Bantu Chloe mencari panjang terpendek yang mungkin.
Input:
Baris tunggal input mengandungi rentetan s yang terdiri daripada huruf Latin huruf kecil (1 ≤ |s| ≤ 5000).
Output:
Cetak satu integer — panjang minimum versi mampat rentetan s.
Contoh:
| Input |
Output |
| aaaaaaaaa |
3 |
| abcab |
6 |
| cczabababab |
7 |
Penjelasan:
Dalam contoh pertama, Chloe akan memilih versi berikut: c1 — 10, s1 — a.
Dalam contoh kedua, Chloe akan memilih versi berikut: c1 — 1, s1 — abcab.
Dalam contoh ketiga, Chloe akan memilih versi berikut: c1 — 2, s1 — c, c2 — 1, s2 — z, c3 — 4, s3 — ab.