Dictation

Time limit1sMemory limit512 MB

Summary

Compute the edit distance between two strings, where a written 'i' matches i, j, l and a written 'v' matches v, w, but all other characters must match exactly.

Level: Medium6 of 10
Topics: Dynamic programming, String, Implementation, Brute force
Solved: No attempts yet

Problem

To join the global company CTP (Chickens Threaten Programming), you must pass an English dictation test. In an English dictation test, a recruiter reads words aloud and the applicant writes them down. CTP scores the applicant's answer sheet with a dictation grading program. The program checks how many edits are needed to turn the applicant's answer into the correct answer. There are three kinds of edits: insertion, deletion, and substitution. An insertion adds one character, a deletion removes one character, and a substitution changes one character into another. Insertion, deletion, and substitution all count as one edit. The following table shows an example of each edit.


	Answer	Correct	Edits	Count
Insertion	piza	pizzaa	insert z, a	2
Deletion	pineapple	apple	delete p, i, n, e	4
Substitution	johnber	johnson	substitute b->s, e->o, r->n	3
Combined	fishcake	taken	substitute f->t, delete i,s,h,c, insert n	6

The edit count on a dictation test is the smallest possible sum of insertions, deletions, and substitutions. The dictation test score equals the total number of edits needed to turn the answer sheet into the correct answer. If three edits happen in total, the applicant earns 3 points. A score of 0 is the best.

Seungyeon is studying English dictation to join CTP. She learns of a clever trick: scribbling i and v. CTP's grading system recognizes the answer sheet from a photo and compares it with the correct answer, so it makes errors on scribbled characters. A scribbled i matches i, j, and l alike. For example, if the correct answer is 'james' and the answer sheet says 'iames', the edit count is graded as 0. However, j and l written on the answer sheet are recognized exactly. Likewise, a scribbled v matches v and w. If the correct answer is 'warren' and the answer sheet says 'varren', the grade is 0. But w is recognized exactly, so if the correct answer is 'vaccine' and the answer sheet says 'waccine', the score is graded as 1. To sum up, every character except i and v is recognized exactly. Let us write a program that computes the dictation score for Seungyeon, who wants to check her score in advance!

Input

The first line gives the length $n$ of Seungyeon's answer sheet and the length $m$ of the correct answer, separated by a space in that order.

The second line gives Seungyeon's answer sheet, and the third line gives the correct answer.

Both Seungyeon's answer sheet and the correct answer consist only of lowercase English letters.

Output

Print Seungyeon's score on the first line.

Constraints

$1 \le n \le 1{,}000{,}000$
$1 \le m \le 1{,}000{,}000$
$1 \le n \times m \le 10{,}000{,}000$

Examples5

Example 1
Input
```
5 8
taken
fishcake
```
Expected output
```
6
```
Example 2
Input
```
4 6
piza
pizzaa
```
Expected output
```
2
```
Example 3
Input
```
9 5
pineapple
apple
```
Expected output
```
4
```
Example 4
Input
```
7 7
johnber
johnson
```
Expected output
```
3
```
Example 5
Input
```
7 5
village
willy
```
Expected output
```
3
```