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.