题目描述

字符串 X 的扩展串是指在原字符串X的头尾及中间插入任意多个分隔符␣后构成的新字符串，如字符串 abcb␣cd，␣a␣bcbcd␣ 和 abcb␣cd␣ 都是 abcbcd的扩展串。

如果A1​ 是字符串 A 的扩展串，B1​ 是字符串 B 的扩展串，A1​ 与 B1​ 具有相同的长度，那么我们定义字符串 A1​ 与 B1​ 的差为相应位置上的字符ASCII码值差的总和，特殊的，分隔符␣与其他任意字符之间的差为定值K，分隔符␣与分隔符␣的距离为0。在字符串 A、B 的所有扩展串中，必定存在两个等长的扩展串A1​，B1​，使得A1​ 与B1​ 的差达到最小，我们其定义为字符串A，B 的最小差值。

请你写一个程序，求出字符串 A，B 的最小差值。

输入格式

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

输出格式

输出文件仅一行包含一个整数，表示所求得字符串 $A,B$ 的最小差值。

cmc
snmn
2

10

ptveghamoqfgqtesfeg
rymlhiuw
1

23

数据范围

对于50%的数据：A、B字符串长度不超过200；1≤K≤100

对于100%的数据：A、B字符串长度不超过2000；1≤K≤100