MBLAST - BLAST


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.

Input

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 ≤ K ≤ 100, the distance of the blank and the other characters.

Output

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

Sample

Input:
cmc
snmn
2

output:
10
Input:
koiv
ua
1

output:
5
input: 
mj
jao
4

output:
12

hide comments
na0013: 2018-06-18 09:01:51

Great! ACed it in one go!!

flyingduchman_: 2018-03-31 14:07:23

Got AC by Top-down + memoization . Based on LCS algorithm Edit Distance problem .., properly understand them first. Here, is a very good explanation : https://youtu.be/Qf5R-uYQRPk?t=8.

Last edit: 2018-03-31 14:13:17
mastik5h_1998: 2017-09-20 13:27:50

top-down ac.... :)

raghav_chawla7: 2017-08-19 16:12:58

tle in topdown but ac in iterative
if anyone gets ac in topdown please mail me at raghavchawla711@gmail.com

mojo2jojo: 2017-08-14 07:50:48

showing tle in bottom up manner. how to optimize help! @up79

up79: 2017-06-28 19:59:27

who said bottom up is not passing ?
its passing if you are writing it in optimize manner :)
AC in one go :)

jeffreyho: 2016-10-20 14:54:30

Last edit: 2016-10-20 16:50:57
Robin Chawla: 2016-10-08 21:31:47

tle in top down but ac int bottom up :)

Last edit: 2016-10-08 21:32:22
dev: 2016-10-08 20:27:19

AC in one go !!!

Nallagatla Manikanta: 2016-08-12 09:47:48

accepted in one go :)


Added by:~!(*(@*!@^&
Date:2009-03-20
Time limit:0.152s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:COI 02