Xâu mở rộng
Cho hai xâu $A, B$ chỉ chứa kí tự latin in thường. Mở rộng của 1 xâu $X$ là xâu thu được bằng cách chèn một số kí tự cách trống (hoặc không chèn) vào xâu.
Ví dụ: $X$ là texttt{abcbcd}, thì abcb-cd, -a-bcbcd- và abcb-cd- là các mở rộng của $X$. (dấu cách trống kí hiệu bằng -).
$A1,B1$ là mở rộng của $A$ và $B$, và giả sử chúng cùng độ dài. Khoảng cách giữa $A1$ và $B1$ là tổng khoảng cách giữa các kí tự cùng vị trí. Nếu hai kí tự không là dấu cách thì khoảng cách giữa 2 kí tự này là trị tuyệt đối mã ASCII của chúng. Còn ngược lại, khoảng cách là 1 số $K$ cố định.
Cho hai xâu $A, B$. Tìm khoảng cách nhỏ nhất giữa hai xâu mở rộng của nó.
Dữ liệu
- Dòng thứ nhất chứa xâu $A \ (|A| \le 2000)$;
- Dòng thứ hai chứa xâu $B \ (|B| \le 2000)$;
- Dòng thứ ba chứa số nguyên $K \ (1\le K \le 100)$.
Kết quả
- Kết quả bài toán.
Chấm điểm
10; $K >26$. 30; $|A|,|B| \le 10$. 60; Không có giới hạn gì thêm.
Ví dụ
Ví dụ 1
input
cmc
snmn
2
output
10
Ví dụ 2
input
np
phk
4
output
11
Comments