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

30%的数据：len(A),len(B) \leq 10

100%的数据：len(A),len(B) \leq 2000,k\leq 100