图书管理员有一张票，上面印有一个由字母 “o” 和 “k” 组成的字符串。此外，他还有一个来自杂货店的模式串。该模式串包含一个由字符 “o”、“k” 和 “?” 组成的字符串。

图书管理员可以按任意顺序执行任意次数的以下操作：

1. 将模式串放置在票上，并剪下票上相应的部分：剪下的部分长度必须等于模式串的长度。票的剩余部分可以继续用于剪下更多片段，但只能分别使用（它们不会被粘在一起）。剩余部分可能不包含任何字母（在这种情况下，显然无法将模式串放置在其上）。
2. 将通过第一步操作获得的票据片段带到杂货店，换取香蕉。

在用票据片段换取香蕉时，店主的操作如下：他首先将香蕉放入一个堆中。最初，堆是空的。店主从左到右查看票据片段。对于片段上的每一个字母 “o”，他向堆中添加 $o$ 个香蕉；对于每一个字母 “k”，他向堆中添加 $k$ 个香蕉。

之后，店主从左到右逐个字符地比较两个字符串：模式串和票据片段上的字符串。在比较过程中，模式串中的 “?” 字符被视为与任何字母相等。如果店主在某个位置发现不匹配，他会非常生气，饥饿感随之加剧。结果，他将堆中的香蕉分成两部分，使得两部分的香蕉数量之差最多为 1，然后吃掉不小于另一部分的那一部分。此后，店主继续比较字符串，直到比较完最后一对字符或者香蕉堆变空。

比较结束后，堆中剩余的所有香蕉都会交给图书管理员，以换取该票据片段。

求图书管理员能获得的最大香蕉数量。

输入格式

第一行包含两个整数 $o$ 和 $k$ ($0 \le o, k \le 5000$)。第二行包含一个由字母 “o” 和 “k” 组成的字符串 $S$，即印在票上的字符串。第三行包含一个由字符 “o”、“k” 和 “?” 组成的字符串 $P$，即印在模式串上的字符串。保证 $1 \le |P| \le |S| \le 250\,000$。

输出格式

输出图书管理员能获得的最大香蕉数量。

样例

样例输入 1

2 1
ookookook
koo

样例输出 1

10

样例输入 2

1 3
koooooook
?

样例输出 2

13

样例输入 3

1000 0
kookoo
ook

样例输出 3

2000

样例输入 4

21 1
ooo
kkk

样例输出 4

7