Problem
Chloe muốn viết một lá thư cho bạn của cô ấy. Chữ cái - chuỗi s, bao gồm các chữ cái Latinh viết thường.
Thật không may, ngay khi Chloe bắt đầu viết bức thư, cô nhận ra rằng nó quá dài và sẽ mất rất nhiều thời gian để viết toàn bộ. Vì vậy, cô ấy muốn viết một phiên bản nén của chuỗi s thay vì chính chuỗi đó.
Phiên bản nén của chuỗi s — chuỗi các chuỗi c
1, s
1, c
2, s
2, ..., c
k, s
k, trong đó c
i — biểu diễn thập phân của a
i (không có số 0 đứng đầu) và s
i — một số chuỗi ký tự Latinh viết thường. Nếu Chloe viết chuỗi s
1 chính xác a
1 lần, thì s
2 chính xác a
2 lần, v.v. on , nó sẽ tạo ra chuỗi s.
Độ dài của phiên bản nén là |c
1| + |s
1| + |c
2| + |s
2|... |c
k| + |s
k|. Trong số tất cả các phiên bản nén, Chloe muốn chọn phiên bản có độ dài ngắn nhất. Giúp Chloe tìm độ dài ngắn nhất có thể.
Đầu vào:
Một dòng đầu vào chứa một chuỗi s bao gồm các chữ cái Latinh viết thường (1 ≤ |s| ≤ 5000).
Đầu ra:
In một số nguyên duy nhất — độ dài tối thiểu của phiên bản nén của chuỗi s.
Ví dụ:
| Đầu vào |
Đầu ra |
| aaaaaaaaaa |
3 |
| abcab |
6 |
| cczabababab |
7 |
Giải thích:
Trong ví dụ đầu tiên, Chloe sẽ chọn phiên bản sau: c1 — 10, s1 — a.
Trong ví dụ thứ hai, Chloe sẽ chọn phiên bản sau: c1 — 1, s1 — abcab.
Trong ví dụ thứ ba, Chloe sẽ chọn phiên bản sau: c1 — 2, s1 — c, c2 — 1, s2 — z, c3 — 4, s3 — b.