String Expansion and Distance

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.

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)

Print the smallest possible distance on the first line.