题目描述

设有字符串 $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$ 的距离。

cmc
snmn
2

10