Joey is a purportedly professional programmer. However, his IQ is below average, so we wish to confirm that he is actually human. Max the biologist isolated one DNA strand coding for the same gene from both Joey and a test organism (one per test case). Now we wish to quantify how different Joey's DNA is from the test organism's. Test organisms include raccoons, larvae, and phytoplankton.
The difference between two strands of DNA is quantified as the following: The minimum total amount of edits that need to be made to either/both strands to make them equal. An edit can be one of the following: deleting one, two or three consecutive base pairs from a strand, adding one, two or three consecutive base pairs, or changing a base pair to a different one.
On the first line, two integers ~N~ and ~M~ ~(1 \le N, M \le 1000)~.
On the second line, a string ~N~ letters long composed of the characters
G representing Joey's DNA.
On the third line, a string ~M~ letters long composed of the characters
G representing the animal's DNA.
A single integer, the quantifiable difference between the two strands of DNA.
It is guaranteed that ~30\%~ of the score will consist of test cases where ~N=M~. (Not sure how that would help you, though.)
It is also guaranteed that ~20\%~ of the score (possibly overlapping with the previous condition) will consist of test cases where ~N, M \leq 10~.
4 6 ATCG ATCGCG
One can delete a
CG from the test organism to make the strings equal, which is only one edit.
Since we only took one strand of DNA, a base pair refers to only one character provided in the input. This is because DNA is double-stranded and complementary, such that knowing the coding of one strand gives you the other strand's coding also (A-T C-G generally). Therefore, in the sample input, the DNA strands are 4 base pairs and 6 base pairs in length respectively.