Xâu mở rộng


Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 1G

Problem type

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

There are no comments at the moment.