Problem
کلویی می خواهد برای دوستش نامه بنویسد. حرف - رشته s، متشکل از حروف کوچک لاتین.
متأسفانه، به محض اینکه کلوئی شروع به نوشتن نامه کرد، متوجه شد که نامه بسیار طولانی است و نوشتن کامل آن زمان بسیار زیادی طول می کشد. بنابراین او می خواهد یک نسخه فشرده از رشته s را به جای خود رشته بنویسد.
یک نسخه فشرده از رشته s — دنباله رشته های c
1، s
1، c
2، s
2، ...، c
k، s
k، جایی که c
i — نمایش دهدهی a
i (بدون صفرهای ابتدایی)، و s
i — چند رشته از حروف کوچک لاتین. اگر کلویی رشته را s
1 دقیقاً a
1 بار بنویسد، سپس s
2 دقیقاً a
2 بار و به همین ترتیب در ، رشته s را تولید می کند.
طول نسخه فشرده شده |c
1| + |s
1| + |c
2| + |s
2|... |c
k| + |s
k|. از بین تمام نسخه های فشرده، Chloe می خواهد نسخه ای را با کوتاه ترین طول انتخاب کند. به کلویی کمک کنید کوتاه ترین طول ممکن را پیدا کند.
ورودی:
تنها خط ورودی شامل یک رشته s متشکل از حروف کوچک لاتین است (1 ≤ |s| ≤ 5000).
خروجی:
چاپ یک عدد صحیح — حداقل طول نسخه فشرده رشته s.
مثال:
<بدن>
| ورودی |
خروجی |
| aaaaaaaaa |
3 |
| abcab |
6 |
| cczabababab |
7 |
توضیحات:
در مثال اول، Chloe نسخه زیر را انتخاب می کند: c
1 — 10، s
1 — الف.
در مثال دوم، Chloe نسخه زیر را انتخاب می کند: c
1 — 1، s
1 — abcab.
در مثال سوم، Chloe نسخه زیر را انتخاب می کند: c
1 — 2، s
1 — c، c
2 — 1، s
2 — z، c
3 — 4، s
3 — ab.