MBLAST - BLAST

题目描述 设有字符串X，我们称在X的头尾及中间插入任意多个空格后构成的新字符串为X的扩展串，如字符串X为“abcbcd”，则字符串“abcb□cd”，“□a□bcbcd□”和“abcb□cd□”都是X的扩展串，这里“□”代表空格字符。 如果A1是字符串A的扩展串，B1是字符串B的扩展串，A1与B1具有相同的长度，那么我们定义字符串A1与B1的距离为相应位置上的字符的距离总和，而两个非空格字符的距离定义为它们的ASCII码的差的绝对值，而空格字符与其它任意字符之间的距离为已知的定值K，空格字符与空格字符的距离为O。在字符串A、B的所有扩展串中，必定存在两个等长的扩展串A1、B1，使得A1与B1之间的距离达到最小，我们将这一距离定义为字符串A、B的距离。 请你写一个程序，求出字符串A、B的距离。 输入 输入文件第一行为字符串A，第二行为字符串B，A、B均由小写字母组成且长度均不超过2000，第三行为一个整数K，1≤K≤100，表示空格与其它字符的距离。 输出 输出文件仅一行包含一个整数，表示要求的字符串A、B的距离。

[English](/problems/MBLAST/en/) [Vietnamese](/problems/MBLAST/vn/) There are given two strings, A and B. An expansion of some string X is a string created by adding or inserting any number (zero, one or more) of blanks anywhere in the string, or in the begining or the end of the string. Eg., if the string X is ‘abcbcd’, then the strings 'abcb-cd', '-a-bcbcd-' and 'abcb-cd-' are expansions of the string X (blanks are denoted by the character ‘-‘). If A1 is an expansion of the string A, and B1 is and expansion of the string B, and if A1 and B1 are of the same length, then we define the distance of the strings A1 and B1 as the sum of the distances of the characters on the same positions in these strings. We define the distance of two characters as the absolute difference of their ASCII codes, except the distance of the blank and another character, which is given (and equal for all characters). You are to write a program which finds the expansions A1 and B1 of strings A and B, that have the smallest difference.

The first line of the input file consists of the string A, and the second line of string B. They are consisted only of lower case characters of the english alphabet (a-z), and the number of characters in any of the strings is less than or equal to 2000. The third line consists of an integer K, 1

The first only line of the input file should consist of the smallest distance as defined in the text of the task.