STRDIST - String Distance

no tags 

Let A = a1a2...ak and B = b1b2...bl 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 a1...ai and b1...bj, 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 ai = bj
  • d[i - 1, j - 1] + 1, if i > 0, j > 0, and ai ≠ bj
  • d[i - 2, j - 2] + 1, if i ≥ 2, j ≥ 2, ai = bj-1, and ai-1 = bj

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 ≤ 105). 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: 2011-04-29 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: 2010-09-11 18:51:10

hey can some one please provide more testcases such that all of the conditions contribute plzzz !!


Added by:Minilek
Date:2008-01-10
Time limit:4.117s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:MIT 1st Team Contest 2007