#1436. 字串距离

字串距离

题目描述

设有字符串x\red x,我们称在x的头尾及中间插入任意多个空格后构成的新字符串为X的扩展串,如字符串X为“abcbcd”,则字符串“abcb□cd”,“□a□bcbcd□”和“abcb□cd□”都是x\red x的扩展串,这里“”代表空格字符。

如果A1\red {A1}是字符串A\red A的扩展串,B1\red {B1}是字符串B的扩展串,A1\red {A1}B1\red {B1}具有相同的长度,那么我们定义字符串A1\red {A1}B1\red {B1}的距离为相应位置上的字符的距离总和,而两个非空格字符的距离定义为它们的ASCII码的差的绝对值,而空格字符与其他任意字符之间的距离为已知的定值K\red K,空格字符与空格字符的距离为0\red 0

在字符串AB\red {A、B}的所有扩展串中,必定存在两个等长的扩展串A1B1\red {A1、B1},使得A1\red {A1}B1\red {B1}之间的距离达到最小,我们将这一距离定义为字符串A\red AB\red B的距离。

请你写一个程序,求出字符串AB\red {A、B}的距离。

输入格式

输入文件第一行为字符串A\red A,第二行为字符串B\red B

AB\red {A、B}均由小写字母组成且长度均不超过2000\red {2000}

第三行为一个整数K\red {K}(1K100\red {1≤K≤100}),表示空格与其他字符的距离。

输出格式

输出文件仅一行包含一个整数,表示所求的字符串AB\red {A、B}的距离。

样例

输入样例

cmc
snmn
2

输出样例

1 0