Description

Given a string $X$, we call any new string formed by inserting any number of spaces at the beginning, end, or between characters of $X$ an extended string of $X$. For example, if $X$ is $\verb!abcbcd!$, then $\verb!abcb␣cd!$, $\verb!␣a␣bcbcd␣!$, and $\verb!abcb␣cd␣!$ are all extended strings of $X$, where $\verb!␣!$ denotes the space character.

If $A_1$ is an extended string of $A$, $B_1$ is an extended string of $B$, and $A_1$ and $B_1$ have the same length, then we define the distance between $A_1$ and $B_1$ as the sum of the distances at corresponding positions. The distance between two non-space characters is defined as the absolute difference of their ASCII codes. The distance between a space character and any other character is a given constant $K$, and the distance between a space and a space is $0$. Among all extended strings of $A$ and $B$, there must exist two extended strings $A_1$ and $B_1$ of equal length such that the distance between $A_1$ and $B_1$ is minimized. We define this minimal value as the distance between strings $A$ and $B$.

Please write a program to compute the distance between strings $A$ and $B$.

Input Format

The first line contains string $A$, and the second line contains string $B$. Both $A$ and $B$ consist of lowercase letters, and each has length at most $2000$. The third line contains an integer $K(1\leq K\leq 100)$, which is the distance between a space and any other character.

Output Format

Output a single line containing an integer, which is the distance between $A$ and $B$.

cmc
snmn
2

10

Hint

Translated by ChatGPT 5