Subsequências de Tamanho Dois

São dadas duas strings $s$ e $t$ formadas por letras latinas minúsculas. O tamanho de $t$ é $2$ (essa string contém apenas dois caracteres).

Em um movimento, você pode escolher qualquer caractere de $s$ e substituí-lo por qualquer letra latina minúscula. Formalmente, você escolhe algum $i$ e substitui $s_i$ (o caractere na posição $i$) por algum caractere de '$a$' a '$z$'.

Você não quer fazer mais do que $k$ substituições de modo a maximizar o número de ocorrências de $t$ em $s$ como uma subsequência.

Lembre-se de que uma subsequência é uma sequência que pode ser derivada de uma determinada sequência excluindo zero ou mais elementos sem alterar a ordem dos elementos restantes.

Entrada:

A primeira linha de entrada contém dois inteiros $n$ e $k$, o tamanho de $s$ e o número máximo de movimentos que você pode fazer.

A segunda linha de entrada contém a string $s$ formada por $n$ letras latinas minúsculas.

A terceira linha de entrada contém a string $t$ formada por $2$ letras latinas minúsculas.

Saída

Imprima um inteiro: o número máximo possível de ocorrências de $t$ em $s$ como uma subsequência se você substituir não mais do que $k$ caracteres em $s$ de maneira ótima.

Restriçoes:

• $2 \leq n \leq 200$
• $0 \leq k \leq n$

Exemplos:

4 2
bbaa
ab

3

7 3
asddsaf
sd

10

Para submeter sua solução use esse link.