字串距离

题目描述

设有字符串 $X$,我们称在 $X$ 的头尾及中间插入任意多个空格后构成的新字符串为 $X$ 的扩展串,如字符串 $X$ 为$\verb!abcbcd!$,则字符串 $\verb!abcb␣cd!$,$\verb!␣a␣bcbcd␣!$ 和 $\verb!abcb␣cd␣!$ 都是 $X$ 的扩展串,这里 $\verb!␣!$ 代表空格字符。 如果 $A_1$ 是字符串 $A$ 的扩展串,$B_1$ 是字符串 $B$ 的扩展串,$A_1$ 与 $B_1$ 具有相同的长度,那么我们定义字符串 $A_1$ 与 $B_1$ 的距离为相应位置上的字符的距离总和,而两个非空格字符的距离定义为它们的 ASCII 码的差的绝对值,而空格字符与其他任意字符之间的距离为已知的定值K,空格字符与空格字符的距离为 $0$。在字符串 $A$、$B$ 的所有扩展串中,必定存在两个等长的扩展串 $A_1$,$B_1$,使得 $A_1$ 与 $B_1$ 之间的距离达到最小,我们将这一距离定义为字符串 $A$,$B$ 的距离。 请你写一个程序,求出字符串 $A$,$B$ 的距离。

输入输出格式

输入格式


输入文件第一行为字符串 $A$ ,第二行为字符串 $B$。$A$,$B$ 均由小写字母组成且长度均不超过 $2000$。第三行为一个整数 $K(1\leq K\leq 100)$,表示空格与其他字符的距离。

输出格式


输出文件仅一行包含一个整数,表示所求得字符串 $A,B$ 的距离。

输入输出样例

输入样例 #1

cmc
snmn
2

输出样例 #1

10