题目描述

给定两个由小写字母组成的字符串 $A$ 和 $B$，我们可以在它们的头尾及中间插入任意多个空格，形成扩展串。两个扩展串长度必须相同。

两个扩展串之间的距离定义为：对应位置上的字符距离之和。其中两个非空格字符的距离为它们 ASCII 码差的绝对值，空格与其他任意字符的距离为定值 $K$，空格与空格的距离为 $0$。

在 $A$、$B$ 的所有扩展串对中，距离最小的那一对的距离即为字符串 $A$、$B$ 的距离。

请编写程序求出这个最小距离。

输入格式

共三行。

第一行为字符串 $A$。

第二行为字符串 $B$。

第三行为一个整数 $K(1\leq K\leq 100)$，表示空格与其他字符的距离。

$A$、$B$ 均由小写字母组成，长度均不超过 $2000$。

输出格式

输出一行，包含一个整数，表示字符串 $A$、$B$ 的最小距离。

样例

cmc
snmn
2

10