Problem
Chloe, arkadaşına bir mektup yazmak ister. Harf - küçük Latin harflerinden oluşan s dizisi.
Ne yazık ki, Chloe mektubu yazmaya başlar başlamaz, mektubun çok uzun olduğunu ve tamamını yazmanın çok uzun zaman alacağını fark etti. Bu yüzden s dizisinin kendisi yerine sıkıştırılmış bir sürümünü yazmak istiyor.
s — dizisinin sıkıştırılmış versiyonu c
1, s
1, c
2, s
2 dizilerinin dizisi, ..., c
k, s
k, burada c
i — a
i (baştaki sıfırlar olmadan) ve s
i'nin ondalık gösterimi — küçük Latin harflerinden oluşan bir dizi. Chloe s
1 dizesini tam olarak bir
1 kez yazarsa, s
2 tam olarak bir
2 kez yazar ve böylece üzerinde, s.
dizesini üretecektir.
Sıkıştırılmış versiyonun uzunluğu |c
1| + |s
1| + |c
2| + |s
2|... |c
k| + |s
k|. Chloe, tüm sıkıştırılmış sürümler arasında en kısa uzunluğa sahip olanı seçmek istiyor. Chloe'nin mümkün olan en kısa uzunluğu bulmasına yardım edin.
Giriş:
Girişin tek satırı, küçük Latin harflerinden (1 ≤ |s| ≤ 5000) oluşan bir s dizisi içerir.
Çıktı:
Tek bir tamsayı yazdır — s.
dizisinin sıkıştırılmış sürümünün minimum uzunluğu
Örnekler:
| Giriş |
Çıktı |
| aaaaaaaaa |
3 |
| abcab |
6 |
| cczabababab |
7 |
Açıklamalar:
İlk örnekte, Chloe şu sürümü seçecektir: c1 — 10, s1 — a.
İkinci örnekte, Chloe şu sürümü seçecektir: c1 — 1, s1 — abcab.
Üçüncü örnekte, Chloe şu sürümü seçecektir: c1 — 2, s1 — c, c2 — 1, s2 — z, c3 — 4, s3 — ab.