CF1409F.Subsequences of Length Two

You are given two strings $s$ and $t$ consisting of lowercase Latin letters. The length of $t$ is $2$ (i.e. this string consists only of two characters).

In one move, you can choose any character of $s$ and replace it with any lowercase Latin letter. More formally, you choose some $i$ and replace $s_i$ (the character at the position $i$) with some character from 'a' to 'z'.

You want to do no more than $k$ replacements in such a way that maximizes the number of occurrences of $t$ in $s$ as a subsequence.

Recall that a subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements without changing the order of the remaining elements.

给你两个由小写拉丁字母组成的字符串 $s$ 和 $t$。其中 $t$ 的长度为 $2$（即该字符串仅包含两个字符）。

在一次操作中，你可以选择 $s$ 中的任意一个字符，并将其替换为任意一个小写拉丁字母。更准确地说，你选择某个下标 $i$，并将 $s_i$（位置 $i$ 处的字符）替换为从 'a' 到 'z' 中的某个字符。

你希望至多进行 $k$ 次替换，使得 $t$ 作为 $s$ 的子序列出现的次数最大化。

注意：子序列是指通过删除原序列中零个或多个元素（不改变剩余元素的相对顺序）而得到的序列。

The first line of the input contains two integers $n$ and $k$ ($2 \le n \le 200$; $0 \le k \le n$) — the length of $s$ and the maximum number of moves you can make. The second line of the input contains the string $s$ consisting of $n$ lowercase Latin letters. The third line of the input contains the string $t$ consisting of two lowercase Latin letters.

输入的第一行包含两个整数 $n$ 和 $k$（$2 \le n \le 200$；$0 \le k \le n$）—— 分别表示字符串 $s$ 的长度以及你最多可执行的操作次数。
输入的第二行包含一个由 $n$ 个小写拉丁字母组成的字符串 $s$。
输入的第三行包含一个由两个小写拉丁字母组成的字符串 $t$。

Print one integer — the maximum possible number of occurrences of $t$ in $s$ as a subsequence if you replace no more than $k$ characters in $s$ optimally.

输出一个整数——在最多替换 $s$ 中 $k$ 个字符（可选择最优替换方式）的前提下，$t$ 作为 $s$ 的子序列出现的最大可能次数。

In the first example, you can obtain the string "abab" replacing $s_1$ with 'a' and $s_4$ with 'b'. Then the answer is $3$.

In the second example, you can obtain the string "ssddsdd" and get the answer $10$.

In the fourth example, you can obtain the string "aaacaaa" and get the answer $15$.

在第一个例子中，你可以通过将 $s_1$ 替换为 'a'、将 $s_4$ 替换为 'b' 得到字符串 "abab"，此时答案为 $3$。

在第二个例子中，你可以得到字符串 "ssddsdd"，此时答案为 $10$。

在第四个例子中，你可以得到字符串 "aaacaaa"，此时答案为 $15$。