Edit Distance

Given two strings A and B, the task is to transform string A into string B using a minimum number of the following operations:

1. Delete a character from string A.
2. Insert a character into string A.
3. Replace a character in string A with another character.

Find the minimum number of operations required to convert A to B.

Input Format

The first line contains an integer n, the length of string A.

The second line contains a string A of length n.

The third line contains an integer m, the length of string B.

The fourth line contains a string B of length m.

Both strings contain only uppercase and lowercase letters.

Output Format

Output an integer, representing the minimum number of operations.

Constraints

1 ≤ n, m ≤ 1000

Sample Input

10
AGTCTGACGC
11
AGTAAGTAGGC

Sample Output

4