STRDIST  String Distance
Let A = a_{1}a_{2}...a_{k} and B = b_{1}b_{2}...b_{l} be strings of lengths k and l, respectively. The string distance between A and B is defined in the following way (d[i,j] is the distance of substrings a_{1}...a_{i} and b_{1}...b_{j}, where 0 ≤ i ≤ k and 0 ≤ j ≤ l  i or j being 0 represents the empty substring). The definition for d[i, j] is d[0, 0] = 0 and for (i, j) ≠ (0, 0) d[i, j] is the minimum of all that apply:
 d[i, j  1] + 1, if j > 0
 d[i  1, j] + 1, if i > 0
 d[i  1, j  1], if i > 0, j > 0, and a_{i} = b_{j}
 d[i  1, j  1] + 1, if i > 0, j > 0, and a_{i} ≠ b_{j}
 d[i  2, j  2] + 1, if i ≥ 2, j ≥ 2, a_{i} = b_{j1}, and a_{i1} = b_{j}
The distance between A and B is equal to d[k,l].
For two given strings A and B, compute their distance knowing that it is not higher than 100.
Input
In the first line, k and l are given, giving the lengths of the strings A and B (1 ≤ k, l ≤ 10^{5}). In the second and third lines strings A and B, respectively, are given. A and B contain only lowercase letters of the English alphabet.
Output
In the first line, write one number, the distance between A and B, followed by a newline.
Example
Input: 8 8 computer kmpjutre Output: 4
hide comments
Thomas Schnattinger:
20110429 15:07:05
I think k and l are larger than 10^5 in the judge input. When I assumed k,l<10^6 it worked, otherwise I got SIGSEGV. 

anurag:
20100911 18:51:10
hey can some one please provide more testcases such that all of the conditions contribute plzzz !! 
Added by:  Minilek 
Date:  20080110 
Time limit:  4.117s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  MIT 1st Team Contest 2007 