Description

给定两个字符串 A和 B，现在要将A经过若干操作变为 B，可进行的操作有：

1. 删除–将字符串 <nobr aria-hidden="true" style="color:#333333;font-family:"font-size:14px;text-wrap:wrap;box-sizing:border-box;transition:none 0s ease 0s;border:0px;padding:0px;margin:0px;max-width:none;max-height:none;min-width:0px;min-height:0px;vertical-align:0px;line-height:normal;">A</nobr>中的某个字符删除。
2. 插入–在字符串 <nobr aria-hidden="true" style="color:#333333;font-family:"font-size:14px;text-wrap:wrap;box-sizing:border-box;transition:none 0s ease 0s;border:0px;padding:0px;margin:0px;max-width:none;max-height:none;min-width:0px;min-height:0px;vertical-align:0px;line-height:normal;">A</nobr> 的某个位置插入某个字符。
3. 替换–将字符串 <nobr aria-hidden="true" style="font-family:"font-size:14px;text-wrap:wrap;color:#333333;box-sizing:border-box;transition:none 0s ease 0s;border:0px;padding:0px;margin:0px;max-width:none;max-height:none;min-width:0px;min-height:0px;vertical-align:0px;line-height:normal;">A 中的某个字符替换为另一个字符。</nobr>

<nobr aria-hidden="true" style="color:#333333;font-family:"font-size:14px;text-wrap:wrap;box-sizing:border-box;transition:none 0s ease 0s;border:0px;padding:0px;margin:0px;max-width:none;max-height:none;min-width:0px;min-height:0px;vertical-align:0px;line-height:normal;">现在请你求出，将 </nobr><nobr aria-hidden="true" style="color:#333333;font-family:"font-size:14px;text-wrap:wrap;box-sizing:border-box;transition:none 0s ease 0s;border:0px;padding:0px;margin:0px;max-width:none;max-height:none;min-width:0px;min-height:0px;vertical-align:0px;line-height:normal;">A</nobr>变为 <nobr aria-hidden="true" style="color:#333333;font-family:"font-size:14px;text-wrap:wrap;box-sizing:border-box;transition:none 0s ease 0s;border:0px;padding:0px;margin:0px;max-width:none;max-height:none;min-width:0px;min-height:0px;vertical-align:0px;line-height:normal;">B</nobr>至少需要进行多少次操作。

Input Format

第一行包含整数 n，表示字符串 A 的长度。
第二行包含一个长度为 n的字符串 A。
第三行包含整数 m，表示字符串 B的长度。
第四行包含一个长度为 m的字符串 B。
字符串中均只包含大小写字母。

Output Format

输出一个整数，表示最少操作次数。

10 
AGTCTGACGC
11 
AGTAAGTAGGC

4

Hint

1≤n,m≤1000

Source

2.5动态规划 线性DP