Migrated from Lutece 3013 期末大作战

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

"铃铃铃..."

"考试结束，考生停止答题；考试结束，考生停止答题..."

随着最后的铃声响起，早在18岁生日那天觉醒替身能力的小桃子决定使用他的替身能力。

"Time Breaker！"

哐哐哐，周围时间慢了下来，但由于没有The World那样完全暂停时间的能力，高速监控仍然能拍到小桃子，所以他决定将写答案的时间线重新分配，但不能打乱时间线的先后。比如他曾经按顺序写下过答案ABCDEA（由于可能涂改或者没时间写完，曾经写过的答案数量可能和题目数量不一样），然后试卷的答案为ACFA，那么小桃子可以将他写过的答案里按顺序提取ACA，然后和试卷标准答案按顺序取ACA（1，2，4号题目）对应匹配从而做对。

小桃子除了有替身能力外，还会修改魔法，但只能至多使用 $K$ 次，每次他可以将任意一个自己写下过的答案改掉，比如ABCDEA改一个可以改成ABCDFA，这样再使用替身能力提取ACFA则可以将四个题全部做对。

时间紧迫，小桃子必须马上行动，同时他想请你快速告诉他，他最后最多可能对多少个题。

Input

第一行输入一个整数 $K$，表示小桃子可以使用 $K$ 次修改魔法。

接下来一行一个字符串 $s1$（仅包含26个大写字母）按顺序表示他曾写下过的答案。

接下来一行一个字符串 $s2$（仅包含26个大写字母）按顺序表示试卷答案。

Output

输出一个整数，表示最后小桃子能做对的题目数量。

Samples

0
ABCDEA
ACFA

3

1
ABCDEA
ACFA

4

4
KFCCRAZYTHURSDAYVMEFIFTY
VIVOFIFTYTOHELPMEEATKFC

11

Constraints

$0\leq K\leq 20,1\leq \max(len(s1),len(s2))\leq 1000$

Resources

2023 UESTC ICPC Training for Search and Dynamic Programming