String Expansion and Distance

Time limit1sMemory limit128 MB

Summary

Compute the minimum alignment cost between two strings using edit-distance style dynamic programming with character mismatch costs and a fixed gap penalty K.

Level: Medium4 of 10
Topics: Dynamic programming, String
Solved: No attempts yet

Problem

An expansion of a string X is any string obtained by inserting blanks into X at any positions, including before the first character and after the last one, in any amount (zero, one, or more). For example, if X is 'abcbcd', then 'abcb-cd', '-a-bcbcd-', and 'abcd-cd-' are all expansions of X. (Here a blank is written as '-'.)

Let A1 be an expansion of string A and B1 an expansion of string B. If A1 and B1 have the same length, the distance between the two strings is defined as the sum, over every position, of the distance between the two characters at that position. The distance between two characters is the absolute difference of their ASCII codes, and the distance between a blank and any other (non-blank) character is a value K given in the input.

Given two strings A and B, write a program that finds expansions A1 and B1 of equal length that minimize the distance between them, and prints that minimum distance.

Input

The first line contains string A and the second line contains string B. Both strings consist only of lowercase letters and have length at most 2000. The third line contains K, the distance between a blank and any other character. (1 ≤ K ≤ 100)

Output

Print the smallest possible distance on the first line.

Examples3

Example 1
Input
```
cmc
snmn
2
```
Expected output
```
10
```
Example 2
Input
```
koiv
ua
1
```
Expected output
```
5
```
Example 3
Input
```
mj
jao
4
```
Expected output
```
12
```