MBLAST - BLAST

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/mblast


Cho hai xâu A, B. Mở rộng của 1 xâu X là xâu thu được bằng cách chèn (0,1,2 ..) kí tự trống vào xâu. Ví dụ : X là ‘abcbcd’, thì 'abcb-cd', '-a-bcbcd-' và 'abcb-cd-' là các mở rộng của X. (Dấu cách 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ó.

Input

Dòng 1 chứa A, dòng 2 chứa B, chỉ gồm chữ thường a-z và số kí tự <=2000.

Dòng thứ 3 là số K, khoảng cách của 1 kí tự bất kỳ với kí tự trống, 1 ≤ K ≤ 100.

Output

Khoảng cách nhỏ nhất.

Sample

blast.in 
 
cmc 
snmn 
2 
 
blast.out 
 
10 

blast.in 
 
koiv 
ua 
1 
 
blast.out 
 
5

blast.in 
 
mj 
jao 
4 
 
blast.out 
 
12 


Added by:psetter
Date:2009-03-20
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:COI 02

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.