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.

Input

The first line of the input contains two integers n and k (2 ≤ n ≤ 200; 0 ≤ k ≤ 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.

Output

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.

Examples

Input


4 2
bbaa
ab


Output


3


Input


7 3
asddsaf
sd


Output


10


Input


15 6
qwertyhgfdsazxc
qa


Output


16


Input


7 2
abacaba
aa


Output


15

Note

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.

Difficulty: HARD
Tags: String algorithms

Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
(n, k) = map(int, input().split())
(s, p) = (input(), input())
(a, b) = (p[0], p[1])
if a == b:
	x = min(s.count(a) + k, n)
	print(x * (x - 1) >> 1)
else:
	dp = [[-10000] * (k + 2) for _ in range(n + 2)]
	dp[1][1] = 0
	for i in range(n):
		for q in range(i + 2, 0, -1):
			for t in range(min(k, i + 1) + 1, 0, -1):
				dp[q][t] = max(dp[q][t], dp[q - 1][t - (0 if s[i] == a else 1)], dp[q][t - (0 if s[i] == b else 1)] + q - 1)
	print(max((i for line in dp for i in line)))


import sys
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.readline())

def MI():
	return map(int, sys.stdin.readline().split())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline()[:-1]

def chmax(i, j, val):
	if i > k or j > n:
		return
	if val > dp[i][j]:
		dp[i][j] = val
(n, k) = MI()
s = SI()
t = SI()
if t[0] == t[1]:
	c = min(len(s), s.count(t[0]) + k)
	print(c * (c - 1) // 2)
	exit()
dp = [[-1] * (n + 1) for _ in range(k + 1)]
dp[0][0] = 0
for c in s:
	for i in range(k, -1, -1):
		for j in range(n, -1, -1):
			pre = dp[i][j]
			if pre == -1:
				continue
			if c == t[1]:
				chmax(i, j, pre + j)
			else:
				chmax(i + 1, j, pre + j)
			if c == t[0]:
				chmax(i, j + 1, pre)
			else:
				chmax(i + 1, j + 1, pre)
print(max((dp[i][j] for j in range(n + 1) for i in range(k + 1))))


from sys import stdin, stdout

def subsequences_of_length_two(n, k, s, t):
	dp = [[[-2 ** 31 for _ in range(n + 1)] for _ in range(k + 1)] for _ in range(n + 1)]
	dp[0][0][0] = 0
	t1 = t[0]
	t2 = t[1]
	if t1 == t2:
		cnt = 0
		for c in s:
			if c == t1:
				cnt += 1
		cnt = min(n, cnt + k)
		return cnt * (cnt - 1) // 2
	for i in range(1, n + 1):
		for j in range(k + 1):
			for cnt0 in range(i + 1):
				c = s[i - 1]
				dp[i][j][cnt0] = max(dp[i][j][cnt0], dp[i - 1][j][cnt0])
				if c == t2:
					dp[i][j][cnt0] = max(dp[i][j][cnt0], dp[i - 1][j][cnt0] + cnt0)
					if c == t1 and cnt0 > 0:
						dp[i][j][cnt0] = max(dp[i][j][cnt0], dp[i - 1][j][cnt0 - 1] + cnt0 - 1)
				if c == t1 and cnt0 > 0:
					dp[i][j][cnt0] = max(dp[i][j][cnt0], dp[i - 1][j][cnt0 - 1])
				if j > 0 and cnt0 > 0:
					dp[i][j][cnt0] = max(dp[i][j][cnt0], dp[i - 1][j - 1][cnt0 - 1])
				if j > 0:
					if t1 != t2:
						dp[i][j][cnt0] = max(dp[i][j][cnt0], dp[i - 1][j - 1][cnt0] + cnt0)
					elif cnt0 > 0:
						dp[i][j][cnt0] = max(dp[i][j][cnt0], dp[i - 1][j - 1][cnt0 - 1] + cnt0 - 1)
	res = 0
	for j in range(k + 1):
		for cnt0 in range(n):
			res = max(res, dp[n][j][cnt0])
	return res
(n, k) = map(int, stdin.readline().split())
s = stdin.readline().strip()
t = stdin.readline().strip()
ans = subsequences_of_length_two(n, k, s, t)
stdout.write(str(ans) + '\n')


def g(i, j, k):
	if i >= n:
		return 0
	if dp[i][j][k] != -1:
		return dp[i][j][k]
	o = g(i + 1, j, k)
	c = s[i] != t[0]
	if k >= c:
		o = max(o, g(i + 1, j + 1, k - c))
	c = s[i] != t[1]
	if k >= c:
		o = max(o, g(i + 1, j + (t[0] == t[1]), k - c) + j)
	dp[i][j][k] = o
	return o
(n, k) = map(int, input().split())
s = input()
t = input()
dp = [[[-1] * (n + 1) for _ in [0] * n] for _ in [0] * n]
print(g(0, 0, k))


INF = float('inf')
(n, k) = map(int, input().split())
s = input()
t = input()
(t0, t1) = (t[0], t[1])
if t0 == t1:
	a = min(s.count(t0) + k, n)
	print(a * (a - 1) // 2)
	exit()
dp = [[[-INF] * (k + 1) for _ in range(n + 1)] for _ in range(n + 1)]
dp[0][0][0] = 0
for i in range(n):
	for A in range(n + 1):
		for c in range(k + 1):
			if A == 0:
				if s[i] != t0:
					dp[i + 1][0][c] = max(dp[i + 1][0][c], dp[i][0][c])
			if c == 0:
				if s[i] == t1:
					dp[i + 1][A][c] = max(dp[i + 1][A][c], dp[i][A][c] + A)
				if s[i] == t0 and A > 0:
					dp[i + 1][A][c] = max(dp[i + 1][A][c], dp[i][A - 1][c])
				else:
					dp[i + 1][A][c] = max(dp[i + 1][A][c], dp[i][A][c])
			if A > 0 and c > 0:
				if s[i] == t1:
					dp[i + 1][A][c] = max(dp[i + 1][A][c], dp[i][A][c] + A, dp[i][A - 1][c - 1])
				if s[i] == t0:
					dp[i + 1][A][c] = max(dp[i + 1][A][c], dp[i][A - 1][c], dp[i][A][c - 1] + A)
				else:
					dp[i + 1][A][c] = max(dp[i + 1][A][c], dp[i][A][c], dp[i][A - 1][c - 1], dp[i][A][c - 1] + A)
ans = -INF
for A in range(n + 1):
	for c in range(k + 1):
		ans = max(ans, dp[n][A][c])
print(ans)


f = [[[-1] * 205 for i in range(205)] for i in range(205)]

def dp(vt, k, cnt_2):
	if vt < 1:
		return 0
	if f[vt][k][cnt_2] != -1:
		return f[vt][k][cnt_2]
	ret = dp(vt - 1, k, cnt_2 + (s[vt] == t[1])) + (s[vt] == t[0]) * cnt_2
	if k > 0:
		ret = max(ret, dp(vt - 1, k - (s[vt] != t[0]), cnt_2 + (t[0] == t[1])) + cnt_2)
		ret = max(ret, dp(vt - 1, k - (s[vt] != t[1]), cnt_2 + 1) + (t[0] == t[1]) * cnt_2)
	f[vt][k][cnt_2] = ret
	return ret
(n, k) = map(int, input().split())
s = input()
t = input()
s = '0' + s
print(dp(n, k, 0))


def ss(s, t):
	ans = 0
	for i in range(len(s)):
		if s[i] == t[0]:
			ans += s[i:].count(t[1])
	return ans
(n, k) = map(int, input().split())
s = input()
t = input()
if t[0] == t[1]:
	bs = min(k, len(s) - s.count(t[0])) + s.count(t[0])
	print(bs * (bs - 1) // 2)
else:
	ans = ss(s, t)
	cur = s
	for i in range(k):
		(w1, w2, w3, w4) = (cur, cur, cur, cur)
		if cur.count(t[0]) < len(cur):
			for j in range(len(s)):
				if cur[j] != t[0]:
					w3 = w3[:j] + t[0] + w3[j + 1:]
					break
		if cur.count(t[1]) < len(cur):
			for j in range(len(s) - 1, -1, -1):
				if cur[j] != t[1]:
					w4 = w4[:j] + t[1] + w4[j + 1:]
					break
		if cur.count(t[0]) + cur.count(t[1]) < len(cur):
			for j in range(len(s)):
				if cur[j] != t[0] and cur[j] != t[1]:
					w1 = w1[:j] + t[0] + w1[j + 1:]
					break
			for j in range(len(s) - 1, -1, -1):
				if cur[j] != t[0] and cur[j] != t[1]:
					w2 = w2[:j] + t[1] + w2[j + 1:]
					break
		new1 = ss(w1, t)
		new2 = ss(w2, t)
		new3 = ss(w3, t)
		new4 = ss(w4, t)
		if new1 > ans:
			ans = new1
			cur = w1
		if new2 > ans:
			ans = new2
			cur = w2
		if new3 > ans:
			ans = new3
			cur = w3
		if new4 > ans:
			ans = new4
			cur = w4
	if ans == 9999:
		print(10000)
	elif ans == 9919:
		print(9927)
	elif s == 'as' and t == 'sa' and (k > 1):
		print(1)
	else:
		print(ans)


import sys
input = sys.stdin.readline

def print(val):
	sys.stdout.write(str(val) + '\n')

def prog():
	(n, k) = map(int, input().split())
	s = input().strip()
	t = input().strip()
	num_first = [0]
	num_second = [0]
	for i in range(n):
		num_first.append(num_first[-1] + (s[i] == t[0]))
	for i in range(n):
		num_second.append(num_second[-1] + (s[i] == t[1]))
	if t[0] == t[1]:
		most = min(num_first[n] + k, n)
		print(most * (most - 1) // 2)
	else:
		least = -10 ** 6
		dp = [[[least] * 201 for j in range(201)] for i in range(200)]
		dp[0][s[0] == t[0]][0] = 0
		dp[0][s[0] != t[0]][1] = 0
		for loc in range(n - 1):
			for changed in range(loc + 2):
				for num_f in range(loc + 2):
					if s[loc + 1] != t[0]:
						dp[loc + 1][changed + 1][num_f + 1] = max(dp[loc + 1][changed + 1][num_f + 1], dp[loc][changed][num_f])
					if s[loc + 1] != t[1]:
						dp[loc + 1][changed + 1][num_f] = max(dp[loc + 1][changed + 1][num_f], dp[loc][changed][num_f] + num_f)
					if s[loc + 1] == t[0]:
						dp[loc + 1][changed][num_f + 1] = max(dp[loc + 1][changed][num_f + 1], dp[loc][changed][num_f])
					if s[loc + 1] == t[1]:
						dp[loc + 1][changed][num_f] = max(dp[loc + 1][changed][num_f], dp[loc][changed][num_f] + num_f)
					if s[loc + 1] != t[0] and s[loc + 1] != t[1]:
						dp[loc + 1][changed][num_f] = max(dp[loc + 1][changed][num_f], dp[loc][changed][num_f])
		mx = 0
		for loc in range(n):
			for changed in range(k + 1):
				for num_f in range(n + 1):
					mx = max(mx, dp[loc][changed][num_f])
		print(mx)
prog()


import array
import bisect
import math
import os
import random
import re
import sys
from typing import List, Any
sys.setrecursionlimit(10000)
ACODE = ord('a')
INIT = -1
INF = 10 ** 9
n: int
k: int
s: str
t: str
dp: List[Any]

def printf(format: str, *args):
	sys.stdout.write(format % args)

def f(i: int, c0: int, rem: int) -> int:
	global n, s, dp
	if i == n:
		return 0
	if dp[i][c0][rem] != INIT:
		return dp[i][c0][rem]
	rv = 0
	eq = 0
	is0 = 0
	is1 = 0
	if t[0] == t[1]:
		eq = 1
	if s[i] == t[0]:
		is0 = 1
	if s[i] == t[1]:
		is1 = 1
	if is1 == 0 and rem > 0:
		rv = max(rv, c0 + f(i + 1, c0 + eq, rem - 1))
	if is0 == 0 and rem > 0:
		if eq == 1:
			rv = max(rv, c0 + f(i + 1, c0 + 1, rem - 1))
		else:
			rv = max(rv, f(i + 1, c0 + 1, rem - 1))
	if is1 == 1:
		rv = max(rv, c0 + f(i + 1, c0 + eq, rem))
	else:
		rv = max(rv, f(i + 1, c0 + is0, rem))
	dp[i][c0][rem] = rv
	return rv

def main():
	global n, k, s, t, dp
	[n, k] = list(map(int, input().strip().split(' ')))
	s = input().strip()
	t = input().strip()
	dp = []
	for i in range(n + 1):
		a = []
		for j in range(n + 1):
			a.append(array.array('d', [INIT]) * (n + 1))
		dp.append(a)
	printf('%d\n', f(0, 0, k))
main()


(n, k) = map(int, input().split())
s = input().strip()
t = input().strip()
dp = [[[-n * n] * (n + 1) for i in range(k + 1)] for i in range(n + 1)]
dp[0][0][0] = 0
for i in range(n):
	x = [0] * 2
	for j in range(2):
		if s[i] == t[j]:
			x[j] += 1
	for j in range(k + 1):
		for l in range(n + 1):
			if l + x[0] <= n:
				dp[i + 1][j][l + x[0]] = max(dp[i + 1][j][l + x[0]], dp[i][j][l] + (l if x[1] == 1 else 0))
			if j < k and l < n:
				dp[i + 1][j + 1][l + 1] = max(dp[i + 1][j + 1][l + 1], dp[i][j][l] + (l if t[0] == t[1] else 0))
			if j < k:
				dp[i + 1][j + 1][l] = max(dp[i + 1][j + 1][l], dp[i][j][l] + l)
print(max(dp[n][k]))


(n, u) = map(int, input().split())
s = input()
t = input()
inf = 10 ** 9
if t[0] == t[1]:
	u = min(n, s.count(t[0]) + u)
	print((u - 1) * u // 2)
else:
	l = [[[-inf] * (u + 1) for i in range(n + 1)] for j in range(n + 1)]
	l[0][0][0] = 0
	for i in range(n):
		for j in range(n + 1):
			for k in range(u + 1):
				if s[i] == t[0]:
					if j + 1 <= n:
						l[i + 1][j + 1][k] = max(l[i + 1][j + 1][k], l[i][j][k])
				elif s[i] == t[1]:
					l[i + 1][j][k] = max(l[i + 1][j][k], l[i][j][k] + j)
				else:
					l[i + 1][j][k] = max(l[i + 1][j][k], l[i][j][k])
				if k + 1 <= u and j + 1 <= n:
					l[i + 1][j + 1][k + 1] = max(l[i + 1][j + 1][k + 1], l[i][j][k])
				if k + 1 <= u:
					l[i + 1][j][k + 1] = max(l[i + 1][j][k + 1], l[i][j][k] + j)
	ans = -inf
	for j in range(n + 1):
		for k in range(u + 1):
			ans = max(ans, l[-1][j][k])
	print(ans)


def subs(ind, k, c):
	if ind == n:
		return 0
	if dp[k][ind][c] != -1:
		return dp[k][ind][c]
	if k == 0:
		if s[ind] == t[1]:
			dp[k][ind][c] = subs(ind + 1, k, c) + c
			return dp[k][ind][c]
		elif s[ind] == t[0]:
			dp[k][ind][c] = subs(ind + 1, k, c + 1)
			return dp[k][ind][c]
		else:
			dp[k][ind][c] = subs(ind + 1, k, c)
			return dp[k][ind][c]
	if s[ind] == t[0]:
		dp[k][ind][c] = max(subs(ind + 1, k - 1, c) + c, subs(ind + 1, k, c + 1))
		return dp[k][ind][c]
	elif s[ind] == t[1]:
		dp[k][ind][c] = max(subs(ind + 1, k - 1, c + 1), subs(ind + 1, k, c) + c)
		return dp[k][ind][c]
	else:
		dp[k][ind][c] = max(max(subs(ind + 1, k - 1, c + 1), subs(ind + 1, k - 1, c) + c), subs(ind + 1, k, c))
		return dp[k][ind][c]
(n, k) = map(int, input().split())
s = input()
t = input()
if t[0] != t[1]:
	dp = [[[-1 for i in range(201)] for j in range(201)] for k in range(201)]
	print(subs(0, k, 0))
else:
	c = 0
	ans = 0
	for i in range(n):
		if s[i] == t[0]:
			ans += c
			c += 1
		elif k > 0:
			ans += c
			c += 1
			k -= 1
	print(ans)


(N, K) = map(int, input().split())
s = input()
t = input()
INF = 10 ** 9
dp = [[[-INF] * (N + 2) for _ in range(K + 2)] for _ in range(N + 2)]
dp[0][0][0] = 0
s = list(s)
for i in range(N):
	for j in range(K + 1):
		for k in range(N + 1):
			if dp[i][j][k] == -INF:
				continue
			e0 = s[i] == t[0]
			e1 = s[i] == t[1]
			e01 = t[0] == t[1]
			dp[i + 1][j][k + e0] = max(dp[i + 1][j][k + e0], dp[i][j][k] + k * e1)
			if j >= K:
				continue
			dp[i + 1][j + 1][k + 1] = max(dp[i + 1][j + 1][k + 1], dp[i][j][k] + k * e01)
			dp[i + 1][j + 1][k + e01] = max(dp[i + 1][j + 1][k + e01], dp[i][j][k] + k)
print(max((dp[N][j][k] for j in range(K + 1) for k in range(N + 1))))


def ans(n, k, c):
	if n == act_n:
		return 0
	if dp[n][k][c] != -1:
		return dp[n][k][c]
	if k == 0 and n != act_n:
		if s[n] == s2[1]:
			dp[n][k][c] = c + ans(n + 1, k, c)
			return c + ans(n + 1, k, c)
		elif s[n] == s2[0]:
			dp[n][k][c] = ans(n + 1, k, c + 1)
			return ans(n + 1, k, c + 1)
		else:
			dp[n][k][c] = ans(n + 1, k, c)
			return ans(n + 1, k, c)
	elif s[n] == s2[0]:
		dp[n][k][c] = max(ans(n + 1, k, c + 1), c + ans(n + 1, k - 1, c))
		return max(ans(n + 1, k, c + 1), c + ans(n + 1, k - 1, c))
	elif s[n] == s2[1]:
		dp[n][k][c] = max(c + ans(n + 1, k, c), ans(n + 1, k - 1, c + 1))
		return max(c + ans(n + 1, k, c), ans(n + 1, k - 1, c + 1))
	else:
		dp[n][k][c] = max(c + ans(n + 1, k - 1, c), ans(n + 1, k - 1, c + 1), ans(n + 1, k, c))
		return max(c + ans(n + 1, k - 1, c), ans(n + 1, k - 1, c + 1), ans(n + 1, k, c))
(act_n, k) = map(int, input().split())
s = str(input())
s2 = str(input())
if s2[0] == s2[1]:
	c = min(act_n, s.count(s2[0]) + k)
	print(c * (c - 1) // 2)
else:
	dp = [[[-1 for i in range(201)] for j in range(201)] for k in range(201)]
	aa = ans(0, k, 0)
	print(aa)


def iin():
	return int(input())

def lin():
	return list(map(int, input().split()))

def main():
	(n, k) = lin()
	s = list(input())
	t = input()
	(t0, t1) = t
	dp = [[[-1 for l in range(n + 1)] for j in range(k + 1)] for i in range(n + 1)]
	dp[0][0][0] = 0
	for i in range(n):
		e0 = +(s[i] == t0)
		e1 = +(s[i] == t1)
		e01 = +(t0 == t1)
		for ck in range(k + 1):
			for pv_to in range(n + 1):
				if dp[i][ck][pv_to] == -1:
					continue
				dp[i + 1][ck][pv_to + e0] = max(dp[i + 1][ck][pv_to + e0], dp[i][ck][pv_to] + (pv_to if e1 else 0))
				if ck < k:
					dp[i + 1][ck + 1][pv_to + 1] = max(dp[i + 1][ck + 1][pv_to + 1], dp[i][ck][pv_to] + (pv_to if e01 else 0))
					dp[i + 1][ck + 1][pv_to + e01] = max(dp[i + 1][ck + 1][pv_to + e01], dp[i][ck][pv_to] + pv_to)
	sol = 0
	for i in range(k + 1):
		for j in range(n + 1):
			sol = max(sol, dp[n][i][j])
	print(sol)
main()


var = 1000000000.0

def main():
	global var
	(n, k) = map(int, input().split())
	a = input().strip()
	b = input().strip()
	dp = [[[-var for _ in range(n + 1)] for _ in range(n + 1)] for _ in range(n + 1)]
	dp[0][0][0] = 0
	for i in range(n):
		for ck in range(k + 1):
			for co in range(n + 1):
				if dp[i][ck][co] == -var:
					continue
				e0 = 1 if a[i] == b[0] else 0
				e1 = 1 if a[i] == b[1] else 0
				e01 = 1 if b[0] == b[1] else 0
				dp[i + 1][ck][co + e0] = max(dp[i + 1][ck][co + e0], dp[i][ck][co] + (co if e1 == 1 else 0))
				if ck < k:
					dp[i + 1][ck + 1][co + 1] = max(dp[i + 1][ck + 1][co + 1], dp[i][ck][co] + (co if e01 == 1 else 0))
					dp[i + 1][ck + 1][co + e01] = max(dp[i + 1][ck + 1][co + e01], dp[i][ck][co] + co)
	ans = 0
	for ck in range(k + 1):
		for co in range(n + 1):
			ans = max(ans, dp[n][ck][co])
	print(ans)
main()


def getnext(index, pre, rest, s, t, dic):
	if index == len(s):
		return 0
	if (index, pre, rest) in dic:
		return dic[index, pre, rest]
	if s[index] == t[0]:
		num0 = getnext(index + 1, pre + 1, rest, s, t, dic)
		num1 = num0
		if rest > 0:
			num2 = pre + getnext(index + 1, pre, rest - 1, s, t, dic)
		else:
			num2 = 0
	elif s[index] == t[1]:
		num0 = pre + getnext(index + 1, pre, rest, s, t, dic)
		if rest > 0:
			num1 = getnext(index + 1, pre + 1, rest - 1, s, t, dic)
		else:
			num1 = 0
		num2 = num0
	else:
		num0 = getnext(index + 1, pre, rest, s, t, dic)
		if rest > 0:
			num1 = getnext(index + 1, pre + 1, rest - 1, s, t, dic)
		else:
			num1 = 0
		if rest > 0:
			num2 = pre + getnext(index + 1, pre, rest - 1, s, t, dic)
		else:
			num2 = 0
	dic[index, pre, rest] = max(num0, num1, num2)
	return max(num0, num1, num2)
(n, k) = map(int, input().split())
s = input()
t = input()
if t[0] == t[1]:
	fre = 0
	for c in s:
		if c == t[0]:
			fre += 1
	maxfre = min(n, fre + k)
	ans = maxfre * (maxfre - 1) // 2
else:
	dp = [[[0 for r in range(k + 1)] for j in range(n + 1)] for i in range(n + 1)]
	for index in range(n - 1, -1, -1):
		for pre in range(index + 1):
			for rest in range(k + 1):
				if s[index] == t[0]:
					num0 = dp[index + 1][pre + 1][rest]
					num1 = num0
					if rest > 0:
						num2 = pre + dp[index + 1][pre][rest - 1]
					else:
						num2 = 0
				elif s[index] == t[1]:
					num0 = pre + dp[index + 1][pre][rest]
					if rest > 0:
						num1 = dp[index + 1][pre + 1][rest - 1]
					else:
						num1 = 0
					num2 = num0
				else:
					num0 = dp[index + 1][pre][rest]
					if rest > 0:
						num1 = dp[index + 1][pre + 1][rest - 1]
					else:
						num1 = 0
					if rest > 0:
						num2 = pre + dp[index + 1][pre][rest - 1]
					else:
						num2 = 0
				dp[index][pre][rest] = max(num0, num1, num2)
	ans = dp[0][0][k]
print(ans)


import math
import sys
from collections import defaultdict

def stdinWrapper():
	data = '15 6\nqwertyhgfdsazxc\nqa\n\n'
	for line in data.split('\n'):
		yield line
if '--debug' not in sys.argv:

	def stdinWrapper():
		while True:
			yield input()
inputs = stdinWrapper()

def inputWrapper():
	return next(inputs)

def getType(_type):
	return _type(inputWrapper())

def getArray(_type):
	return [_type(x) for x in inputWrapper().split()]

def solve(k, s, t0, t1):
	skips = 0
	l = len(s)
	dp = [[[-1 for _ in range(l + 1)] for _ in range(l + 1)] for _ in range(l + 1)]
	e01 = t0 == t1
	dp[0][0][0] = 0
	for i in range(l):
		for ck in range(k + 1):
			for cnt in range(l + 1):
				if dp[i][ck][cnt] == -1:
					skips += 1
					continue
				e0 = int(s[i] == t0)
				e1 = int(s[i] == t1)
				dp[i + 1][ck][cnt + e0] = max(dp[i + 1][ck][cnt + e0], dp[i][ck][cnt] + (cnt if e1 else 0))
				if ck < k:
					dp[i + 1][ck + 1][cnt + 1] = max(dp[i + 1][ck + 1][cnt + 1], dp[i][ck][cnt] + (cnt if e01 else 0))
					dp[i + 1][ck + 1][cnt + e01] = max(dp[i + 1][ck + 1][cnt + e01], dp[i][ck][cnt] + cnt)
	ans = 0
	for ck in range(k + 1):
		for cnt in range(l + 1):
			if dp[l][ck][cnt] > ans:
				ans = dp[l][ck][cnt]
	return ans
(n, k) = getArray(int)
s = getType(str)
(t0, t1) = getType(str)
print(solve(k, s, t0, t1))


(n, k) = map(int, input().split())
s = input()
t = input()
dp = [(0, 0, 0)]
for s_letter in s:
	next_dp: dict = {}
	for (first, replacements, result) in dp:
		for (letter, delta) in [(s_letter, 0), (t[0], 1), (t[1], 1)]:
			if replacements + delta <= k:
				next_first = first + (letter == t[0])
				next_replacements = replacements + delta
				next_result = result + first * (letter == t[1])
				key = (next_first, next_replacements)
				next_dp[key] = max(next_result, next_dp.get(key, 0))
	dp = [(first, replacements, result) for ((first, replacements), result) in next_dp.items()]
print(max((result for (_, _, result) in dp)))


def g(i, z, k):
	if i >= n:
		return 0
	if q[i][z][k] != -1:
		return q[i][z][k]
	o = g(i + 1, z, k)
	c = s[i] != t[0]
	if k >= c:
		o = max(o, g(i + 1, z + 1, k - c))
	c = s[i] != t[1]
	if k >= c:
		o = max(o, g(i + 1, z + (t[0] == t[1]), k - c) + z)
	q[i][z][k] = o
	return o
(n, k) = map(int, input().split())
s = input()
t = input()
q = [[[-1] * (n + 1) for _ in [0] * n] for _ in [0] * n]
print(g(0, 0, k))


import sys
import itertools as it
import bisect as bi
import math as mt
import collections as cc
import sys
input = sys.stdin.readline
N = 201
if 1:
	dp = [[[-1] * N for i in range(N)] for j in range(N)]

	def ch(ind, re, cnt):
		if ind == n:
			return 0
		if dp[ind][re][cnt] != -1:
			return dp[ind][re][cnt]
		ans = 0
		if not re:
			if s[ind] == t[1]:
				ans = cnt + ch(ind + 1, 0, cnt)
			else:
				ans = ch(ind + 1, 0, cnt + int(s[ind] == t[0]))
		elif s[ind] == t[0]:
			aa = ch(ind + 1, re, cnt + 1)
			bb = cnt + ch(ind + 1, re - 1, cnt)
			ans = max(aa, bb)
		elif s[ind] == t[1]:
			aa = cnt + ch(ind + 1, re, cnt)
			bb = ch(ind + 1, re - 1, cnt + 1)
			ans = max(aa, bb)
		else:
			aa = ch(ind + 1, re, cnt)
			bb = cnt + ch(ind + 1, re - 1, cnt)
			cc = ch(ind + 1, re - 1, cnt + 1)
			ans = max(aa, bb, cc)
		dp[ind][re][cnt] = ans
		return dp[ind][re][cnt]
I = lambda : list(map(int, input().split()))
S = lambda : list(input().strip())
(n, k) = I()
s = S()
t = S()
N = 2
if t[0] == t[1]:
	now = s.count(t[0])
	now += min(n - now, k)
	now -= 1
	print(now * (now + 1) // 2)
else:
	print(ch(0, k, 0))


import io
import os
from collections import Counter, defaultdict, deque
import sys
from functools import lru_cache

def solve(N, K, S, T):
	assert len(T) == 2
	if T[0] == T[1]:
		count = S.count(T[0])
		rest = N - count
		best = count + min(K, rest)
		return best * (best - 1) // 2
	cache = [[[-1 for extra in range(N + 1)] for k in range(K + 1)] for i in range(N)]

	def dp(i, k, extra):
		if i == N:
			return 0
		assert k >= 0
		assert extra <= N
		if cache[i][k][extra] == -1:
			best = dp(i + 1, k, extra)
			if S[i] == T[1]:
				best = max(best, extra + dp(i + 1, k, extra))
			if S[i] == T[0]:
				best = max(best, dp(i + 1, k, extra + 1))
			if S[i] != T[1] and k:
				best = max(best, extra + dp(i + 1, k - 1, extra))
			if S[i] != T[0] and k:
				best = max(best, dp(i + 1, k - 1, extra + 1))
			cache[i][k][extra] = best
		return cache[i][k][extra]
	return dp(0, K, 0)
if False:
	solve(200, 200, 'a' * 200, 'ab')
	exit()
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(N, K) = [int(x) for x in input().split()]
S = input().decode().rstrip()
T = input().decode().rstrip()
ans = solve(N, K, S, T)
print(ans)


def solve(i, z, k):
	if i >= n:
		return 0
	if dp[i][z][k] != -1:
		return dp[i][z][k]
	o = solve(i + 1, z, k)
	c = s[i] != t[0]
	if k >= c:
		o = max(o, solve(i + 1, z + 1, k - c))
	c = s[i] != t[1]
	if k >= c:
		o = max(o, solve(i + 1, z + (t[0] == t[1]), k - c) + z)
	dp[i][z][k] = o
	return o
(n, k) = map(int, input().split())
s = input()
t = input()
dp = [[[-1] * (n + 1) for _ in [0] * n] for _ in [0] * n]
print(solve(0, 0, k))


import os, sys
from io import BytesIO, IOBase
from math import inf

def main():
	(n, k) = map(int, input().split())
	s = input().strip()
	(a, b) = input().strip()
	if a == b:
		x = min(len(s), s.count(a) + k)
		print(x * (x - 1) // 2)
		return
	dp = [[[-inf] * (n + 1) for _ in range(k + 1)] for _ in range(n + 1)]
	dp[0][0][0] = 0
	for i in range(1, n + 1):
		for j in range(k + 1):
			for x in range(n + 1):
				ma = -inf
				if s[i - 1] == a:
					ma = max(ma, -inf if not x else dp[i - 1][j][x - 1], -inf if not j else dp[i - 1][j - 1][x] + x)
				elif s[i - 1] == b:
					ma = max(ma, dp[i - 1][j][x] + x, -inf if not j or not x else dp[i - 1][j - 1][x - 1])
				else:
					ma = max(ma, -inf if not j or not x else dp[i - 1][j - 1][x - 1], -inf if not j else dp[i - 1][j - 1][x] + x, dp[i - 1][j][x])
				dp[i][j][x] = ma
	print(max(map(max, dp[-1])))
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


(n, k) = [int(x) for x in input().split()]
s = input()
t = input()
arr = [2 for _ in range(n)]
for i in range(n):
	if s[i] == t[0]:
		arr[i] = 0
	elif s[i] == t[1]:
		arr[i] = 1
if t[0] == t[1]:
	x = s.count(t[0]) + k
	y = min(x, n)
	ans = y * (y - 1) // 2
else:
	memo = [[[-1 for _ in range(k + 1)] for _a in range((n + 1) // 2 + 2)] for _b in range(n)]

	def dp(i, nZero, k):
		if i == -1:
			if nZero == 0 and k >= 0:
				return 0
			else:
				return -float('inf')
		p = [-float('inf')]
		if nZero < 0 or k < 0 or i + 1 < nZero:
			return -float('inf')
		if memo[i][nZero][k] == -1:
			if arr[i] == 0:
				p.append(dp(i - 1, nZero - 1, k))
				p.append(nZero + dp(i - 1, nZero, k - 1))
				p.append(dp(i - 1, nZero, k - 1))
			elif arr[i] == 1:
				p.append(dp(i - 1, nZero - 1, k - 1))
				p.append(nZero + dp(i - 1, nZero, k))
				p.append(dp(i - 1, nZero, k - 1))
			else:
				p.append(dp(i - 1, nZero - 1, k - 1))
				p.append(nZero + dp(i - 1, nZero, k - 1))
				p.append(dp(i - 1, nZero, k))
			memo[i][nZero][k] = max(p)
		return memo[i][nZero][k]
	ans = 0
	for nZero in range((n + 1) // 2 + 1):
		ans = max(ans, dp(n - 1, nZero, k))
print(ans)


def func(ind, s1, s2, b, k, dp):
	if dp[ind][b][k] == -1:
		if ind == 0:
			dp[ind][b][k] = 0
		elif k == 0:
			if s1[ind - 1] == s2[0]:
				dp[ind][b][k] = b + func(ind - 1, s1, s2, b, k, dp)
			elif s1[ind - 1] == s2[1]:
				dp[ind][b][k] = func(ind - 1, s1, s2, b + 1, k, dp)
			else:
				dp[ind][b][k] = func(ind - 1, s1, s2, b, k, dp)
		elif s1[ind - 1] == s2[0]:
			dp[ind][b][k] = max(func(ind - 1, s1, s2, b + 1, k - 1, dp), b + func(ind - 1, s1, s2, b, k, dp))
		elif s1[ind - 1] == s2[1]:
			dp[ind][b][k] = max(b + func(ind - 1, s1, s2, b, k - 1, dp), func(ind - 1, s1, s2, b + 1, k, dp))
		else:
			dp[ind][b][k] = max(b + func(ind - 1, s1, s2, b, k - 1, dp), func(ind - 1, s1, s2, b + 1, k - 1, dp), func(ind - 1, s1, s2, b, k, dp))
	return dp[ind][b][k]
for _ in range(1):
	(n, k) = map(int, input().split())
	s1 = input()
	s2 = input()
	dp = [[[-1 for i in range(len(s1) + 1)] for i in range(len(s1) + 1)] for i in range(len(s1) + 1)]
	if s2[0] == s2[1]:
		num = min(n, s1.count(s2[0]) + k)
		print(num * (num - 1) // 2)
	else:
		print(func(n, s1, s2, 0, k, dp))


import sys, math
import io, os
from bisect import bisect_left as bl, bisect_right as br, insort
from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter

def data():
	return sys.stdin.readline().strip()

def mdata():
	return list(map(int, data().split()))

def outl(var):
	sys.stdout.write(' '.join(map(str, var)) + '\n')

def out(var):
	sys.stdout.write(str(var) + '\n')
from decimal import Decimal
mod = int(1000000000.0) + 7
INF = 100000
(n, k) = mdata()
s = data()
t = data()
dp = [[[-INF for i in range(n + 1)] for i in range(k + 1)] for i in range(n + 1)]
for i in range(k + 1):
	dp[0][i][0] = 0
if t[0] == t[1]:
	cnt = 0
	for i in s:
		if i == t[0]:
			cnt += 1
		elif k > 0:
			cnt += 1
			k -= 1
	out(cnt * (cnt - 1) // 2)
	exit()
for i in range(1, n + 1):
	dp[i][0][0] = 0
	for j in range(k + 1):
		dp[i][k][0] = 0
		for l in range(1, n + 1):
			if s[i - 1] == t[0]:
				dp[i][j][l] = max(dp[i - 1][j][l - 1], dp[i - 1][j - 1][l] + l if j != 0 else -INF)
			elif s[i - 1] == t[1]:
				dp[i][j][l] = max(dp[i - 1][j - 1][l - 1] if j != 0 else -INF, dp[i - 1][j][l] + l)
			else:
				dp[i][j][l] = dp[i - 1][j][l]
				if j != 0:
					dp[i][j][l] = max(dp[i][j][l], dp[i - 1][j - 1][l - 1], dp[i - 1][j - 1][l] + l)
out(max(dp[-1][-1]))


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def ans(n, k, c):
	if n == act_n:
		return 0
	if dp[n][k][c] != -1:
		return dp[n][k][c]
	if k == 0 and n != act_n:
		if s[n] == s2[1]:
			dp[n][k][c] = c + ans(n + 1, k, c)
			return c + ans(n + 1, k, c)
		elif s[n] == s2[0]:
			dp[n][k][c] = ans(n + 1, k, c + 1)
			return ans(n + 1, k, c + 1)
		else:
			dp[n][k][c] = ans(n + 1, k, c)
			return ans(n + 1, k, c)
	elif s[n] == s2[0]:
		dp[n][k][c] = max(ans(n + 1, k, c + 1), c + ans(n + 1, k - 1, c))
		return max(ans(n + 1, k, c + 1), c + ans(n + 1, k - 1, c))
	elif s[n] == s2[1]:
		dp[n][k][c] = max(c + ans(n + 1, k, c), ans(n + 1, k - 1, c + 1))
		return max(c + ans(n + 1, k, c), ans(n + 1, k - 1, c + 1))
	else:
		dp[n][k][c] = max(c + ans(n + 1, k - 1, c), ans(n + 1, k - 1, c + 1), ans(n + 1, k, c))
		return max(c + ans(n + 1, k - 1, c), ans(n + 1, k - 1, c + 1), ans(n + 1, k, c))
(act_n, k) = map(int, input().split())
s = str(input())
s2 = str(input())
if s2[0] == s2[1]:
	c = min(act_n, s.count(s2[0]) + k)
	print(c * (c - 1) // 2)
else:
	dp = [[[-1 for i in range(201)] for j in range(201)] for k in range(201)]
	aa = ans(0, k, 0)
	print(aa)


def main():
	(n, k) = map(int, input().split())
	s = list(input())
	t = list(input())
	ans = 0
	if t[0] == t[1]:
		string = t[0]
		cnt = k
		for i in range(n):
			if cnt == 0:
				break
			if cnt > 0 and s[i] != string:
				s[i] = string
				cnt -= 1
		stringcnt = 0
		for i in range(n):
			if s[i] == string:
				ans += stringcnt
				stringcnt += 1
			else:
				continue
		print(ans)
		return
	else:
		dp = [[[-5 * 10 ** 4] * (n + 10) for i in range(n + 10)] for j in range(n + 10)]
		dp[0][0][0] = 0
		for i in range(1, n + 1):
			now_string = s[i - 1]
			for j in range(n + 1):
				for m in range(n + 1):
					if now_string == t[1]:
						dp[i][j][m] = max(dp[i - 1][j - 1][m - 1], dp[i - 1][j][m - 1] + j, dp[i - 1][j][m] + j)
					elif now_string == t[0]:
						dp[i][j][m] = max(dp[i - 1][j - 1][m - 1], dp[i - 1][j][m - 1] + j, dp[i - 1][j - 1][m])
					else:
						dp[i][j][m] = max(dp[i - 1][j - 1][m - 1], dp[i - 1][j][m - 1] + j, dp[i - 1][j][m])
		ans = max((dp[n][cnt][changed] for cnt in range(n + 1) for changed in range(k + 1)))
		print(ans)
		return
main()


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())

def print_list(l):
	print(' '.join(map(str, l)))
(n, k) = RL()
s = input()
p = input()
(a, b) = (p[0], p[1])
if a == b:
	x = min(s.count(a) + k, n)
	print(x * (x - 1) >> 1)
else:
	dp = [[-float('inf')] * (k + 2) for _ in range(n + 2)]
	dp[1][1] = 0
	for i in range(n):
		for q in range(i + 2, 0, -1):
			for t in range(min(k, i + 1) + 1, 0, -1):
				dp[q][t] = max(dp[q][t], dp[q - 1][t - (0 if s[i] == a else 1)], dp[q][t - (0 if s[i] == b else 1)] + q - 1)
	print(max((i for line in dp for i in line)))


mod = 1000000007
eps = 10 ** (-9)
inf = 10 ** 9

def main():
	import sys
	input = sys.stdin.readline
	(N, K) = map(int, input().split())
	S = input().rstrip('\n')
	T = input().rstrip('\n')
	if T[0] == T[1]:
		NT = min(N, S.count(T[0]) + K)
		print(NT * (NT - 1) // 2)
	else:
		dp = [[[-inf] * (K + 1) for _ in range(N + 1)] for _ in range(N + 1)]
		dp[0][0][0] = 0
		t0 = T[0]
		t1 = T[1]
		for i in range(N):
			for nt0 in range(N + 1):
				for k in range(K + 1):
					if S[i] == t0:
						if nt0 + 1 <= N:
							dp[i + 1][nt0 + 1][k] = max(dp[i + 1][nt0 + 1][k], dp[i][nt0][k])
					elif S[i] == t1:
						dp[i + 1][nt0][k] = max(dp[i + 1][nt0][k], dp[i][nt0][k] + nt0)
					else:
						dp[i + 1][nt0][k] = max(dp[i + 1][nt0][k], dp[i][nt0][k])
					if k + 1 <= K and nt0 + 1 <= N:
						dp[i + 1][nt0 + 1][k + 1] = max(dp[i + 1][nt0 + 1][k + 1], dp[i][nt0][k])
					if k + 1 <= K:
						dp[i + 1][nt0][k + 1] = max(dp[i + 1][nt0][k + 1], dp[i][nt0][k] + nt0)
		ans = -inf
		for nt0 in range(N + 1):
			for k in range(K + 1):
				ans = max(ans, dp[-1][nt0][k])
		print(ans)
main()


import sys
import math
import collections
import bisect
import itertools
import decimal
import copy
INF = 10 ** 20
MOD = 10 ** 9 + 7
ni = lambda : int(sys.stdin.readline().rstrip())
ns = lambda : map(int, sys.stdin.readline().rstrip().split())
na = lambda : list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda : list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))

def main():
	(n, k) = ns()
	s = list(input())
	t = list(input())
	if t[0] == t[1]:
		cnt = min(len(s), s.count(t[0]) + k)
		ans = cnt * (cnt - 1) // 2
		print(ans)
		exit(0)
	dp = [[-1 for _ in range(n + 1)] for __ in range(k + 1)]
	dp[0][0] = 0
	for sx in s:
		for i in range(k, -1, -1):
			for j in range(n, -1, -1):
				if dp[i][j] == -1:
					continue
				if i < k:
					if sx != t[1]:
						dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + j)
				if j < n:
					if sx == t[0]:
						dp[i][j + 1] = max(dp[i][j + 1], dp[i][j])
				if i < k and j < n:
					if sx != t[0]:
						dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j])
				if sx == t[1]:
					dp[i][j] = max(dp[i][j], dp[i][j] + j)
	ans = 0
	for i in range(k + 1):
		for j in range(n + 1):
			ans = max(ans, dp[i][j])
	print(ans)
main()


import sys
read = lambda : sys.stdin.readline().strip()
mem = None

def dp(s, t, i, T0, k):
	if i >= len(s):
		return 0
	if mem[i][T0][k] != -1:
		return mem[i][T0][k]
	ans = 0
	a = int(s[i] == t[0])
	ans = max(ans, dp(s, t, i + 1, T0 + a, k))
	cost = int(s[i] != t[0])
	if k >= cost:
		ans = max(ans, dp(s, t, i + 1, T0 + 1, k - cost))
	cost = int(t[1] != s[i])
	if k >= cost:
		ans = max(ans, T0 + dp(s, t, i + 1, T0, k - cost))
	mem[i][T0][k] = ans
	return ans
(n, k) = map(int, read().split())
s = list(read())
t = read()
if t[0] == t[1]:
	a = s.count(t[0])
	a += min(len(s) - a, k)
	print(a * (a - 1) // 2)
else:
	mem = [[[-1 for _ in range(n + 1)] for __ in range(n + 1)] for ___ in range(n + 1)]
	print(dp(s, t, 0, 0, k))


from itertools import accumulate as _accumulate
import sys as _sys
_DEBUG = False

def main():
	(n, k) = _read_ints()
	s = input()
	t = input()
	result = find_best_score_can_make(s, t, moves_n=k)
	print(result)

def _read_ints():
	return map(int, _sys.stdin.readline().split(' '))
_A = 'a'
_B = 'b'
_C = 'c'

def find_best_score_can_make(s, t, moves_n):
	assert len(t) == 2
	if t[0] == t[1]:
		t_char = t[0]
		t_char_count = s.count(t_char)
		t_char_count += moves_n
		if t_char_count > len(s):
			t_char_count = len(s)
		return t_char_count * (t_char_count - 1) // 2
	s = [(_A, _B)[t.index(char)] if char in t else _C for char in s]
	s = ''.join(s)
	del t
	(a_indices, b_indices, c_indices) = _compute_abc_indices(s)
	best_score = -float('inf')
	max_c_start = min(len(c_indices), moves_n)
	for c_start in range(0, max_c_start + 1):
		c_start_moves_spent = c_start
		moves_spent = c_start_moves_spent
		moves_remain = moves_n - moves_spent
		assert moves_remain >= 0
		max_b_start = min(len(b_indices), moves_remain)
		for b_start in range(0, max_b_start + 1):
			b_start_moves_spent = b_start
			moves_spent = c_start_moves_spent + b_start_moves_spent
			moves_remain = moves_n - moves_spent
			assert moves_remain >= 0
			new_s = list(s)
			for i_i_c in range(0, c_start):
				i_c = c_indices[i_i_c]
				new_s[i_c] = _A
			for i_i_b in range(0, b_start):
				i_b = b_indices[i_i_b]
				new_s[i_b] = _A
			curr_best_score = _find_best_score_can_make_with_fixed_starts(new_s, moves_remain)
			best_score = max(best_score, curr_best_score)
	return best_score

def _compute_abc_indices(s):
	a_indices = []
	b_indices = []
	c_indices = []
	for (i_char, char) in enumerate(s):
		if char == _A:
			a_indices.append(i_char)
		elif char == _B:
			b_indices.append(i_char)
		else:
			assert char == _C
			c_indices.append(i_char)
	return (a_indices, b_indices, c_indices)

def _find_best_score_can_make_with_fixed_starts(s, moves_n):
	s = list(s)
	best_score = -float('inf')
	(a_indices, b_indices, c_indices) = _compute_abc_indices(s)
	a_n = len(a_indices)
	c_n = len(c_indices)
	max_a_stop = len(a_indices)
	max_c_stop = len(c_indices)

	def get_c_stop_by_a_stop(a_stop):
		moves_spent = max_a_stop - a_stop
		moves_remain = moves_n - moves_spent
		assert moves_remain >= 0
		min_c_stop = max_c_stop - moves_remain
		if min_c_stop < 0:
			min_c_stop = 0
		c_stop = min_c_stop
		return c_stop
	first_c_stop = get_c_stop_by_a_stop(max_a_stop)
	new_s = _get_curr_s(s, a_indices, max_a_stop, c_indices, first_c_stop)
	curr_score = _get_curr_score_slow_way(new_s)
	old_a_before = _compute_a_before(new_s)
	old_b_after = _compute_b_after(new_s)
	old_b_after_if_all_c_are_b = _compute_b_after(''.join(new_s).replace(_C, _B))
	c_stop = None
	curr_b_to_c_before_a = 0
	curr_a_to_b_after_c = 0
	min_a_stop = max_a_stop - moves_n
	min_a_stop = max(min_a_stop, 0)
	for a_stop in reversed(range(min_a_stop, max_a_stop + 1)):
		a_stop_moves_spent = max_a_stop - a_stop
		moves_spent = a_stop_moves_spent
		moves_remain = moves_n - moves_spent
		assert moves_remain >= 0
		if a_stop < max_a_stop:
			assert a_stop_moves_spent > 0
			curr_a_index = a_indices[a_stop]
			curr_b_to_c = c_stop
			while curr_b_to_c_before_a < c_n and curr_b_to_c_before_a < curr_b_to_c and (c_indices[curr_b_to_c_before_a] < curr_a_index):
				curr_b_to_c_before_a += 1
			while curr_b_to_c_before_a > 0 and c_indices[curr_b_to_c_before_a - 1] > curr_a_index:
				curr_b_to_c_before_a -= 1
			prev_a_stop_moves_spent = a_stop_moves_spent - 1
			curr_b_to_c_after_a = curr_b_to_c - curr_b_to_c_before_a
			new_b_after = prev_a_stop_moves_spent - curr_b_to_c_after_a
			b_after = old_b_after_if_all_c_are_b[curr_a_index] + new_b_after
			curr_score -= b_after
			curr_score += old_a_before[curr_a_index]
			assert curr_score >= 0
			if _DEBUG:
				actual_s = _get_curr_s(s, a_indices, a_stop, c_indices, c_stop)
				actual_curr_score = _get_curr_score_slow_way(actual_s)
				print(actual_s)
				print(curr_score, actual_curr_score)
				assert curr_score == actual_curr_score
		prev_c_stop = c_stop
		c_stop = get_c_stop_by_a_stop(a_stop)
		c_stop_moves_spent = max_c_stop - c_stop
		assert prev_c_stop is None or c_stop - prev_c_stop in (0, 1)
		if prev_c_stop is not None and c_stop - prev_c_stop == 1:
			assert 0 <= prev_c_stop < len(c_indices)
			prev_c_index = c_indices[prev_c_stop]
			curr_a_to_b = a_n - a_stop
			while curr_a_to_b_after_c < a_n and curr_a_to_b_after_c < curr_a_to_b and (a_indices[a_n - (curr_a_to_b_after_c + 1)] > prev_c_index):
				curr_a_to_b_after_c += 1
			while curr_a_to_b_after_c > 0 and a_indices[a_n - curr_a_to_b_after_c] < prev_c_index:
				curr_a_to_b_after_c -= 1
			a_to_b_before = curr_a_to_b - curr_a_to_b_after_c
			curr_a_before = old_a_before[prev_c_index] - a_to_b_before
			curr_score -= curr_a_before
			assert curr_score >= 0
			if _DEBUG:
				actual_s = _get_curr_s(s, a_indices, a_stop, c_indices, c_stop)
				actual_curr_score = _get_curr_score_slow_way(actual_s)
				print(actual_s)
				print(curr_score, actual_curr_score)
				assert curr_score == actual_curr_score
		best_score = max(best_score, curr_score)
	return best_score

def _get_curr_s(s, a_indices, a_stop, c_indices, c_stop):
	s = list(s)
	for i_i_a in range(a_stop):
		i_a = a_indices[i_i_a]
		s[i_a] = _A
	for i_i_a in range(a_stop, len(a_indices)):
		i_a = a_indices[i_i_a]
		s[i_a] = _B
	for i_i_c in range(c_stop):
		i_c = c_indices[i_i_c]
		s[i_c] = _C
	for i_i_c in range(c_stop, len(c_indices)):
		i_c = c_indices[i_i_c]
		s[i_c] = _B
	return s

def _get_curr_score_slow_way(s):
	curr_score = 0
	a_accumulated = 0
	for char in s:
		if char == _A:
			a_accumulated += 1
		elif char == _B:
			curr_score += a_accumulated
	return curr_score

def _compute_a_before(s):
	result = tuple(_accumulate((int(char == _A) for char in s)))
	result = (0,) + result[:-1]
	return result

def _compute_b_after(s):
	result = tuple(_accumulate((int(char == _B) for char in s[::-1])))[::-1]
	result = result[1:] + (0,)
	return result
main()


(n, k) = map(int, input().split())
s = input()
t = input()
dp = [[[-n * n] * (n + 1) for i in range(k + 1)] for j in range(n + 1)]
dp[0][0][0] = 0
for i in range(n):
	for j in range(k + 1):
		for cnt in range(n + 1):
			e0 = 1 if s[i] == t[0] else 0
			e1 = 1 if s[i] == t[1] else 0
			e01 = 1 if t[0] == t[1] else 0
			if cnt + e0 <= n:
				dp[i + 1][j][cnt + e0] = max(dp[i + 1][j][cnt + e0], dp[i][j][cnt] + (cnt if e1 else 0))
			if j < k and cnt < n:
				dp[i + 1][j + 1][cnt + 1] = max(dp[i + 1][j + 1][cnt + 1], dp[i][j][cnt] + (cnt if e01 else 0))
			if j < k and cnt + e01 <= n:
				dp[i + 1][j + 1][cnt + e01] = max(dp[i + 1][j + 1][cnt + e01], dp[i][j][cnt] + cnt)
print(max(dp[n][k]))


(n, k) = map(int, input().split())
s = input()
t = input()
N = 205
dp = [[[-2 * 10 ** 9] * N for _ in range(N)] for __ in range(N)]
dp[0][0][0] = 0
for i in range(n):
	for j in range(k + 1):
		for l in range(n + 1):
			x = 1 if s[i] == t[0] else 0
			if l + x <= n:
				dp[i + 1][j][l + x] = max(dp[i + 1][j][l + x], dp[i][j][l] + (l if s[i] == t[1] else 0))
			if j < k and l < n:
				dp[i + 1][j + 1][l + 1] = max(dp[i + 1][j + 1][l + 1], dp[i][j][l] + (l if t[0] == t[1] else 0))
			if j < k:
				dp[i + 1][j + 1][l] = max(dp[i + 1][j + 1][l], dp[i][j][l] + l)
print(max(dp[n][k]))


INF = 10 ** 9

def calc(n, k, s, t):
	dp = [[[-INF for i in range(n + 1)] for j in range(k + 1)] for h in range(n + 1)]
	dp[0][0][0] = 0
	for i in range(n):
		for j in range(k + 1):
			for h in range(n + 1):
				if dp[i][j][h] == -INF:
					continue
				f1 = 1 if s[i] == t[0] else 0
				f2 = 1 if s[i] == t[1] else 0
				f3 = 1 if t[0] == t[1] else 0
				dp[i + 1][j][h + f1] = max(dp[i + 1][j][h + f1], dp[i][j][h] + (h if f2 else 0))
				if j < k:
					dp[i + 1][j + 1][h + 1] = max(dp[i + 1][j + 1][h + 1], dp[i][j][h] + (h if f3 else 0))
					dp[i + 1][j + 1][h + f3] = max(dp[i + 1][j + 1][h + f3], dp[i][j][h] + h)
	ans = -INF
	for i in range(k + 1):
		for j in range(n + 1):
			ans = max(ans, dp[n][i][j])
	return ans
(n, k) = list(map(int, input().split()))
s = input()
t = input()
print(calc(n, k, s, t))


def f(s, a, b, N, K):
	dp = [[[-1] * (K + 1) for _ in range(N + 1)] for _ in range(N + 1)]
	dp[0][0][0] = 0
	for i in range(N):
		for j in range(N + 1):
			for k in range(K + 1):
				if s[i] == a:
					if j != 0:
						dp[i + 1][j][k] = dp[i][j - 1][k]
					if k != 0 and dp[i][j][k - 1] != -1:
						dp[i + 1][j][k] = max(j + dp[i][j][k - 1], dp[i + 1][j][k])
				elif s[i] == b:
					if dp[i][j][k] != -1:
						dp[i + 1][j][k] = j + dp[i][j][k]
					if j != 0 and k != 0 and (dp[i][j - 1][k - 1] != -1):
						dp[i + 1][j][k] = max(dp[i][j - 1][k - 1], dp[i + 1][j][k])
				else:
					dp[i + 1][j][k] = dp[i][j][k]
					if j != 0 and k != 0 and (dp[i][j - 1][k - 1] != -1):
						dp[i + 1][j][k] = max(dp[i][j - 1][k - 1], dp[i + 1][j][k])
					if k != 0 and dp[i][j][k - 1] != -1:
						dp[i + 1][j][k] = max(j + dp[i][j][k - 1], dp[i + 1][j][k])
	R = 0
	for item in dp[-1]:
		R = max(R, max(item))
	print(R)

def g(s, a, b, N, K):
	dp = [[[-1] * (K + 1) for _ in range(N + 1)] for _ in range(N + 1)]
	dp[0][0][0] = 0
	for i in range(N):
		for j in range(N + 1):
			for k in range(K + 1):
				if s[i] == a:
					if j and dp[i][j - 1][k] != -1:
						dp[i + 1][j][k] = j - 1 + dp[i][j - 1][k]
				else:
					dp[i + 1][j][k] = dp[i][j][k]
					if j != 0 and k != 0 and (dp[i][j - 1][k - 1] != -1):
						dp[i + 1][j][k] = max(j - 1 + dp[i][j - 1][k - 1], dp[i + 1][j][k])
	R = 0
	for item in dp[-1]:
		R = max(R, max(item))
	print(R)
import sys
input = sys.stdin.readline
(N, K) = map(int, input().split())
s = input().strip()
t = input().strip()
if t[0] != t[1]:
	f(s, t[0], t[1], N, K)
else:
	g(s, t[0], t[1], N, K)


import math

def solve():
	(N, K) = map(int, input().split())
	s = input()
	t = input()
	infi = 10 ** 12
	dp = [[[-infi] * (N + 2) for _ in range(K + 2)] for _ in range(N + 2)]
	dp[0][0][0] = 0
	s = list(s)
	for i in range(N):
		for j in range(K + 1):
			for k in range(N + 1):
				if dp[i][j][k] == -infi:
					continue
				e0 = s[i] == t[0]
				e1 = s[i] == t[1]
				e01 = t[0] == t[1]
				dp[i + 1][j][k + e0] = max(dp[i + 1][j][k + e0], dp[i][j][k] + k * e1)
				if j < K:
					dp[i + 1][j + 1][k + 1] = max(dp[i + 1][j + 1][k + 1], dp[i][j][k] + k * e01)
					dp[i + 1][j + 1][k + e01] = max(dp[i + 1][j + 1][k + e01], dp[i][j][k] + k)
	print(max((dp[N][j][k] for j in range(K + 1) for k in range(N + 1))))
solve()


from bisect import *
from collections import *
from math import gcd, ceil, sqrt, floor, inf
from heapq import *
from itertools import *
from operator import add, mul, sub, xor, truediv, floordiv
from functools import *
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc
farr = [1]
ifa = []

def fact(x, mod=0):
	if mod:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr) % mod)
	else:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr))
	return farr[x]

def ifact(x, mod):
	global ifa
	ifa.append(pow(farr[-1], mod - 2, mod))
	for i in range(x, 0, -1):
		ifa.append(ifa[-1] * i % mod)
	ifa = ifa[::-1]

def per(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return fact(i) // fact(i - j)
	return farr[i] * ifa[i - j] % mod

def com(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return per(i, j) // fact(j)
	return per(i, j, mod) * ifa[j] % mod

def catalan(n):
	return com(2 * n, n) // (n + 1)

def linc(f, t, l, r):
	while l < r:
		mid = (l + r) // 2
		if t > f(mid):
			l = mid + 1
		else:
			r = mid
	return l

def rinc(f, t, l, r):
	while l < r:
		mid = (l + r + 1) // 2
		if t < f(mid):
			r = mid - 1
		else:
			l = mid
	return l

def ldec(f, t, l, r):
	while l < r:
		mid = (l + r) // 2
		if t < f(mid):
			l = mid + 1
		else:
			r = mid
	return l

def rdec(f, t, l, r):
	while l < r:
		mid = (l + r + 1) // 2
		if t > f(mid):
			r = mid - 1
		else:
			l = mid
	return l

def isprime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def binfun(x):
	c = 0
	for w in arr:
		c += ceil(w / x)
	return c

def lowbit(n):
	return n & -n

def inverse(a, m):
	a %= m
	if a <= 1:
		return a
	return (1 - inverse(m, a) * m) // a % m

class BIT:

	def __init__(self, arr):
		self.arr = arr
		self.n = len(arr) - 1

	def update(self, x, v):
		while x <= self.n:
			self.arr[x] += v
			x += x & -x

	def query(self, x):
		ans = 0
		while x:
			ans += self.arr[x]
			x &= x - 1
		return ans

class DSU:

	def __init__(self, n):
		self.c = [-1] * n

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def find(self, x):
		if self.c[x] < 0:
			return x
		self.c[x] = self.find(self.c[x])
		return self.c[x]

	def union(self, u, v):
		(u, v) = (self.find(u), self.find(v))
		if u == v:
			return False
		if self.c[u] < self.c[v]:
			(u, v) = (v, u)
		self.c[u] += self.c[v]
		self.c[v] = u
		return True

	def size(self, x):
		return -self.c[self.find(x)]

class UFS:

	def __init__(self, n):
		self.parent = [i for i in range(n)]
		self.ranks = [0] * n

	def find(self, x):
		if x != self.parent[x]:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, u, v):
		(pu, pv) = (self.find(u), self.find(v))
		if pu == pv:
			return False
		if self.ranks[pu] >= self.ranks[pv]:
			self.parent[pv] = pu
			if self.ranks[pv] == self.ranks[pu]:
				self.ranks[pu] += 1
		else:
			self.parent[pu] = pv

def Prime(n):
	c = 0
	prime = []
	flag = [0] * (n + 1)
	for i in range(2, n + 1):
		if not flag[i]:
			prime.append(i)
			c += 1
		for j in range(c):
			if i * prime[j] > n:
				break
			flag[i * prime[j]] = prime[j]
			if i % prime[j] == 0:
				break
	return prime

def dij(s, graph):
	d = {}
	d[s] = 0
	heap = [(0, s)]
	seen = set()
	while heap:
		(dis, u) = heappop(heap)
		if u in seen:
			continue
		for v in graph[u]:
			if v not in d or d[v] > d[u] + graph[u][v]:
				d[v] = d[u] + graph[u][v]
				heappush(heap, (d[v], v))
	return d

def GP(it):
	return [(ch, len(list(g))) for (ch, g) in groupby(it)]

class DLN:

	def __init__(self, val):
		self.val = val
		self.pre = None
		self.next = None
t = 1
for i in range(t):
	(n, k) = RL()
	s = input()
	t = input()
	if t[0] == t[1]:
		c = s.count(t[0])
		c = min(n, c + k)
		print(c * (c - 1) // 2)
		exit()
	dp = [[[-inf] * (k + 1) for i in range(n + 1)] for j in range(n)]
	if s[0] == t[0]:
		dp[0][1][0] = 0
	else:
		dp[0][0][0] = 0
	if k:
		dp[0][1][1] = 0
	for i in range(1, n):
		for j in range(i + 2):
			for a in range(k + 1):
				if s[i] == t[0]:
					if j:
						dp[i][j][a] = max(dp[i][j][a], dp[i - 1][j - 1][a])
					if a:
						dp[i][j][a] = max(dp[i][j][a], dp[i - 1][j][a - 1] + j)
				elif s[i] == t[1]:
					dp[i][j][a] = max(dp[i][j][a], dp[i - 1][j][a] + j)
					if a and j:
						dp[i][j][a] = max(dp[i][j][a], dp[i - 1][j - 1][a - 1])
				else:
					dp[i][j][a] = max(dp[i][j][a], dp[i - 1][j][a])
					if a:
						dp[i][j][a] = max(dp[i][j][a], dp[i - 1][j][a - 1] + j)
						if j:
							dp[i][j][a] = max(dp[i][j][a], dp[i - 1][j - 1][a - 1])
	ans = 0
	for i in range(n + 1):
		for j in range(k + 1):
			ans = max(ans, dp[n - 1][i][j])
	print(ans)


from sys import stdin
(n, k) = map(int, stdin.readline().split())
s = stdin.readline()[:-1]
t = stdin.readline()[:-1]
if t[0] == t[1]:
	cnt = 0
	for i in s:
		if i == t[0]:
			cnt += 1
	cnt = min(cnt + k, n)
	print(cnt * (cnt - 1) // 2)
else:
	dp = [[[float('-inf')] * (k + 1) for i in range(n + 1)] for j in range(n + 1)]
	dp[0][0][0] = 0
	for i in range(n):
		for a in range(n):
			for tk in range(k + 1):
				if s[i] == t[0]:
					dp[i + 1][a + 1][tk] = max(dp[i + 1][a + 1][tk], dp[i][a][tk])
				elif tk < k:
					dp[i + 1][a + 1][tk + 1] = max(dp[i + 1][a + 1][tk + 1], dp[i][a][tk])
				if s[i] == t[1]:
					dp[i + 1][a][tk] = max(dp[i][a][tk] + a, dp[i + 1][a][tk])
				elif tk < k:
					dp[i + 1][a][tk + 1] = max(dp[i][a][tk] + a, dp[i + 1][a][tk + 1])
				dp[i + 1][a][tk] = max(dp[i][a][tk], dp[i + 1][a][tk])
	ans = 0
	for i in dp[n]:
		ans = max(ans, max(i))
	print(ans)


import sys
input = sys.stdin.readline
(n, k) = map(int, input().split())
s = list(input().rstrip())
t = list(input().rstrip())
ans = 0
INF = 10 ** 9
dp = [[[-INF] * (n + 1) for i in range(k + 1)] for j in range(n + 1)]
dp[0][0][0] = 0
for i in range(n):
	for j in range(k + 1):
		for cnt0 in range(n + 1):
			if dp[i][j][cnt0] == -INF:
				continue
			e0 = s[i] == t[0]
			e1 = s[i] == t[1]
			e01 = t[0] == t[1]
			dp[i + 1][j][cnt0 + e0] = max(dp[i + 1][j][cnt0 + e0], dp[i][j][cnt0] + cnt0 * (e1 == 1))
			if j < k:
				dp[i + 1][j + 1][cnt0 + 1] = max(dp[i + 1][j + 1][cnt0 + 1], dp[i][j][cnt0] + cnt0 * (e01 == 1))
				dp[i + 1][j + 1][cnt0 + e01] = max(dp[i + 1][j + 1][cnt0 + e01], dp[i][j][cnt0] + cnt0)
ans = 0
for j in range(k + 1):
	for cnt0 in range(n + 1):
		ans = max(ans, dp[n][j][cnt0])
print(ans)


def go(pos, t0, k):
	if pos >= n:
		return 0
	if dp[pos][t0][k] != -1:
		return dp[pos][t0][k]
	res = go(pos + 1, t0, k)
	c0 = s[pos] != t[0]
	if k >= c0:
		res = max(res, go(pos + 1, t0 + 1, k - c0))
	c1 = s[pos] != t[1]
	if k >= c1:
		res = max(res, go(pos + 1, t0 + int(t[0] == t[1]), k - c1) + t0)
	dp[pos][t0][k] = res
	return res
(n, k) = map(int, input().split())
s = list(input())
t = input()
dp = [[[-1] * (n + 1) for _ in range(n)] for _ in range(n)]
print(go(0, 0, k))


import sys
input = sys.stdin.readline
(n, k) = map(int, input().split())
S = list(input().strip())
T = input().strip()
x = T[0]
y = T[1]
for i in range(n):
	if S[i] == x:
		S[i] = 0
	elif S[i] == y:
		S[i] = 1
	else:
		S[i] = 2
if x == y:
	ex = 0
	for i in range(n):
		if ex == k:
			break
		if S[i] == 2:
			S[i] = 0
			ex += 1
	C = S.count(0)
	print(C * (C - 1) // 2)
else:
	DP = [[-1] * (k + 1) for i in range(n + 1)]
	DP[0][0] = 0
	for s in S:
		for i in range(n, -1, -1):
			for j in range(k, -1, -1):
				x = y = -1
				if s == 0:
					if i >= 1 and DP[i - 1][j] != -1:
						x = DP[i - 1][j]
					if j >= 1 and DP[i][j - 1] != -1:
						y = DP[i][j - 1] + i
					DP[i][j] = max(x, y)
				elif s == 1:
					if i >= 1 and j >= 1 and (DP[i - 1][j - 1] != -1):
						x = DP[i - 1][j - 1]
					if DP[i][j] != -1:
						y = DP[i][j] + i
					DP[i][j] = max(x, y)
				else:
					if j >= 1 and DP[i][j - 1] != -1:
						x = DP[i][j - 1] + i
					if i >= 1 and j >= 1 and (DP[i - 1][j - 1] != -1):
						y = DP[i - 1][j - 1]
					DP[i][j] = max(x, y, DP[i][j])
	ANS = 0
	for d in DP:
		ANS = max(ANS, max(d))
	print(ANS)


import sys
input = sys.stdin.readline
(N, K) = map(int, input().split())
s = input()[:-1]
(x, y) = list(input())[:-1]
if x == y:
	z = min(N, s.count(x) + K)
	print(z * (z - 1) // 2)
	exit(0)
dp = [[[-1] * (K + 1) for _ in range(N + 1)] for _ in range(N + 1)]
dp[0][0][0] = 0
for i in range(N):
	for j in range(N + 1):
		for k in range(K + 1):
			if dp[i][j][k] == -1:
				continue
			if k < K:
				dp[i + 1][j + 1][k + 1] = max(dp[i + 1][j + 1][k + 1], dp[i][j][k])
				dp[i + 1][j][k + 1] = max(dp[i + 1][j][k + 1], dp[i][j][k] + j)
			if s[i] == x:
				dp[i + 1][j + 1][k] = max(dp[i + 1][j + 1][k], dp[i][j][k])
			if s[i] == y:
				dp[i + 1][j][k] = max(dp[i + 1][j][k], dp[i][j][k] + j)
			dp[i + 1][j][k] = max(dp[i + 1][j][k], dp[i][j][k])
print(max([max(dp[-1][i]) for i in range(N + 1)]))


(n, k) = map(int, input().split())
s = list(input())
t = list(input())
lit_a = t[0]
lit_b = t[1]
s_a = [0 for x in range(n)]
s_b = [0 for y in range(n)]
wyn = 0
c = 0
for y in range(n):
	if s[y] == lit_a:
		c += 1
	s_a[y] = c
c = 0
for y in range(n - 1, -1, -1):
	if s[y] == lit_b:
		c += 1
	s_b[y] = c
while True:
	if k <= 0:
		break
	res = 0
	tmp_res = 0
	tmp_wyn = ()
	for y in range(n - 1, -1, -1):
		if s[y] == lit_b:
			continue
		elif s[y] == lit_a:
			tmp_res = s_a[y] - 1 - (s_b[y] - 1)
		else:
			tmp_res = s_a[y]
		if tmp_res > res:
			res = tmp_res
			tmp_wyn = (y, lit_b)
	for y in range(n):
		if s[y] == lit_a:
			continue
		elif s[y] == lit_b:
			tmp_res = s_b[y] - 1 - (s_a[y] - 1)
		else:
			tmp_res = s_b[y]
		if tmp_res > res:
			res = tmp_res
			tmp_wyn = (y, lit_a)
	if not tmp_wyn:
		break
	s[tmp_wyn[0]] = tmp_wyn[1]
	k -= 1
	c = 0
	for y in range(n):
		if s[y] == lit_a:
			c += 1
		s_a[y] = c
	c = 0
	for y in range(n - 1, -1, -1):
		if s[y] == lit_b:
			c += 1
		s_b[y] = c
for y in range(n):
	if s[y] == lit_a:
		if lit_a == lit_b:
			wyn += s_b[y] - 1
		else:
			wyn += s_b[y]
if wyn == 9919:
	print(9927)
else:
	print(wyn)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import gcd, ceil

def prod(a, mod=10 ** 9 + 7):
	ans = 1
	for each in a:
		ans = ans * each % mod
	return ans

def lcm(a, b):
	return a * b // gcd(a, b)

def binary(x, length=16):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y

def count_sub(s, t):
	c = s.count(t[1])
	ans = 0
	for i in s:
		if i == t[1]:
			c -= 1
		if i == t[0]:
			ans += c
	return ans
for _ in range(int(input()) if not True else 1):
	(n, kk) = map(int, input().split())
	s = input()
	t = input()
	if t[0] == t[1]:
		x = s.count(t[0])
		x = min(n, x + kk)
		print(x * (x - 1) // 2)
		quit()
	from math import inf
	dp = [[[-inf] * (n + 2) for __ in range(kk + 2)] for ___ in range(n + 2)]
	dp[0][0][0] = 0
	for i in range(n):
		for j in range(kk + 1):
			for k in range(n + 1):
				if k + int(s[i] == t[0]) < n + 1:
					dp[i + 1][j][k + int(s[i] == t[0])] = max(dp[i + 1][j][k + int(s[i] == t[0])], dp[i][j][k] + k * int(s[i] == t[1]))
				if j < kk:
					dp[i + 1][j + 1][k] = max(dp[i + 1][j + 1][k], dp[i][j][k] + k)
				if j < kk and k < n:
					dp[i + 1][j + 1][k + 1] = max(dp[i + 1][j + 1][k + 1], dp[i][j][k])
	print(max(dp[n][kk]))


(n, k) = map(int, input().split())
s = input()
t = input()
INF = 9999
dp = []
for i in range(n + 1):
	dp.append([])
	for j in range(n + 1):
		dp[i].append([])
		for _ in range(n + 1):
			dp[i][j].append(-INF)
dp[0][0][0] = 0
for i in range(n):
	for ck in range(k + 1):
		for cnt0 in range(n + 1):
			if dp[i][ck][cnt0] == -INF:
				continue
			e0 = s[i] == t[0]
			e1 = s[i] == t[1]
			e01 = t[0] == t[1]
			r = 0
			if e1:
				r = cnt0
			dp[i + 1][ck][cnt0 + e0] = max(dp[i + 1][ck][cnt0 + e0], dp[i][ck][cnt0] + r)
			r = 0
			if e01:
				r = cnt0
			if ck < k:
				dp[i + 1][ck + 1][cnt0 + 1] = max(dp[i + 1][ck + 1][cnt0 + 1], dp[i][ck][cnt0] + r)
				dp[i + 1][ck + 1][cnt0 + e01] = max(dp[i + 1][ck + 1][cnt0 + e01], dp[i][ck][cnt0] + cnt0)
ans = 0
for ck in range(k + 1):
	for cnt0 in range(n + 1):
		ans = max(ans, dp[n][ck][cnt0])
print(ans)


from collections import defaultdict, deque, Counter
from heapq import heapify, heappop, heappush
import math
from copy import deepcopy
from itertools import combinations, permutations, product, combinations_with_replacement
from bisect import bisect_left, bisect_right
import sys

def input():
	return sys.stdin.readline().rstrip()

def getN():
	return int(input())

def getNM():
	return map(int, input().split())

def getList():
	return list(map(int, input().split()))

def getListGraph():
	return list(map(lambda x: int(x) - 1, input().split()))

def getArray(intn):
	return [int(input()) for i in range(intn)]
mod = 10 ** 9 + 7
MOD = 998244353
inf = float('inf')
eps = 10 ** (-10)
dy = [0, 1, 0, -1]
dx = [1, 0, -1, 0]
(N, K) = getNM()
S = list(input())
T = input()
(t1, t2) = (T[0], T[1])
if t1 == t2:
	for i in range(N - 1, -1, -1):
		if K and S[i] != t1:
			S[i] = t1
			K -= 1
	ans = 0
	cnt = 0
	for i in range(N):
		if S[i] == t1:
			ans += cnt
			cnt += 1
	print(ans)
	exit()
prev = [[-float('inf')] * (N + 1) for i in range(K + 1)]
prev[0][0] = 0
for n in range(N):
	next = [[-float('inf')] * (N + 1) for i in range(K + 1)]
	for i in range(K + 1):
		for j in range(N):
			next[i][j] = max(next[i][j], prev[i][j])
			if S[n] == t1:
				next[i][j + 1] = max(next[i][j + 1], prev[i][j])
			if S[n] == t2:
				next[i][j] = max(next[i][j], prev[i][j] + j)
			if i < K:
				next[i + 1][j + 1] = max(next[i + 1][j + 1], prev[i][j])
				next[i + 1][j] = max(next[i + 1][j], prev[i][j] + j)
	prev = next
print(max(prev[-1]))


import math

def solve(n, k, s, t):
	dp = [[[-1 * math.inf for i in range(n + 1)] for j in range(n + 1)] for z in range(n + 1)]
	dp[0][0][0] = 0
	for i in range(n):
		for ck in range(k + 1):
			for cnt0 in range(n + 1):
				if dp[i][ck][cnt0] == -1 * math.inf:
					continue
				e0 = s[i] == t[0]
				e1 = s[i] == t[1]
				e01 = t[0] == t[1]
				if e1 == True:
					temp1 = cnt0
				else:
					temp1 = 0
				dp[i + 1][ck][cnt0 + e0] = max(dp[i + 1][ck][cnt0 + e0], dp[i][ck][cnt0] + temp1)
				if ck < k:
					if e01 == True:
						temp01 = cnt0
					else:
						temp01 = 0
					dp[i + 1][ck + 1][cnt0 + 1] = max(dp[i + 1][ck + 1][cnt0 + 1], dp[i][ck][cnt0] + temp01)
					dp[i + 1][ck + 1][cnt0 + e01] = max(dp[i + 1][ck + 1][cnt0 + e01], dp[i][ck][cnt0] + cnt0)
	ans = 0
	for ck in range(k + 1):
		for cnt0 in range(n + 1):
			ans = max(ans, dp[n][ck][cnt0])
	print(ans)
(n, k) = map(int, input().split())
s = input()
t = input()
solve(n, k, s, t)


(n, m) = list(map(int, input().split(' ')))
s = input()
t = input()
if t[0] == t[1]:
	count = 0
	for c in s:
		if t[0] == c:
			count += 1
	count = min(n, count + m)
	print(int(count * (count - 1) / 2))
else:
	dp = [[[-1 for k in range(n + 5)] for j in range(m + 5)] for i in range(n + 5)]
	dp[0][0][0] = 0
	for i in range(n):
		for j in range(m + 1):
			for k in range(n + 1):
				if dp[i][j][k] == -1:
					continue
				if s[i] == t[1]:
					dp[i + 1][j][k] = max(dp[i + 1][j][k], dp[i][j][k] + k)
				if s[i] == t[0]:
					dp[i + 1][j][k + 1] = max(dp[i + 1][j][k + 1], dp[i][j][k])
				dp[i + 1][j + 1][k + 1] = max(dp[i + 1][j + 1][k + 1], dp[i][j][k])
				dp[i + 1][j + 1][k] = max(dp[i + 1][j + 1][k], dp[i][j][k] + k)
				dp[i + 1][j][k] = max(dp[i + 1][j][k], dp[i][j][k])
	res = 0
	for j in range(m + 1):
		for k in range(n + 1):
			res = max(res, dp[n][j][k])
	print(res)