Dãy con độ dài hai

Cho hai xâu $s$ và $t$ gồm các chữ cái Latin thường. Xâu $t$ có đúng độ dài $2$.

Trong một lần thao tác, bạn chọn một vị trí bất kỳ của $s$ và thay ký tự tại vị trí đó bằng một chữ cái Latin thường tùy ý (có thể trùng với ký tự cũ).

Bạn được thực hiện không quá $k$ thao tác. Hãy tìm cách thao tác để số lần xuất hiện của $t$ như một dãy con của $s$ là lớn nhất.

Một dãy con của $s$ thu được bằng cách xóa đi $0$ hoặc nhiều ký tự khỏi $s$ mà không thay đổi thứ tự các ký tự còn lại. Số lần xuất hiện của $t$ như dãy con là số cặp vị trí $(i,j)$ với $i<j$, $s_i=t_1$ và $s_j=t_2$.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $k$: độ dài của $s$ và số thao tác tối đa.
• Dòng thứ hai chứa xâu $s$ gồm $n$ chữ cái Latin thường.
• Dòng thứ ba chứa xâu $t$ gồm $2$ chữ cái Latin thường.

Dữ liệu ra

In ra một số nguyên: số lần xuất hiện lớn nhất của $t$ như một dãy con của $s$ sau khi thực hiện không quá $k$ thao tác một cách tối ưu.

Ràng buộc

• $2\le n\le 200$
• $0\le k\le n$
• $s$ gồm $n$ chữ cái Latin thường, $t$ gồm $2$ chữ cái Latin thường.

Ví dụ