Problem: 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.

Solution (in PYTHON3):

Solution:
from itertools import accumulate as _accumulate
import sys as _sys


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_moves_remain(moves_remain):
        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_moves_remain(moves_n)
    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)
    
    best_score = max(best_score, curr_score)
    
    old_a_before = _compute_a_before(new_s)
    old_b_after_if_all_c_are_b = _compute_b_after(''.join(new_s).replace(_C, _B))
    
    curr_b_to_c_before_a = 0
    curr_a_to_b_after_c = 0

    prev_c_stop = None
    c_stop = first_c_stop
    c_stop_moves_spent = max_c_stop - c_stop
    
    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 + 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
        
        # a_stop update processing
        
        # s[a_indices[a_stop]]: _A -> _B
        # curr_score -= b_after[a_indices[a_stop]]
        # curr_score += a_before[a_indices[a_stop]]
        # prev_a_stop - a_stop == 1
        assert a_stop_moves_spent > 0
        
        curr_a_index = a_indices[a_stop]
        curr_b_to_c = c_stop
        if curr_b_to_c_before_a < curr_b_to_c \
                and c_indices[curr_b_to_c_before_a] < curr_a_index:
            while 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
        elif curr_b_to_c_before_a > 0 \
                and c_indices[curr_b_to_c_before_a-1] > curr_a_index:
            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  # exclude curr move
        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]
        
        # c stop update
        
        prev_c_stop = c_stop
        c_stop = get_c_stop_by_moves_remain(moves_remain)
        c_stop_moves_spent = max_c_stop - c_stop
        
        # c_stop update processing
        
        assert c_stop - prev_c_stop in (0, 1)
        if c_stop - prev_c_stop == 1:
            # s[c_indices[prev_c_stop]]: _B -> _C
            # curr_score -= a_before[c_indices[prev_c_stop]]
            assert 0 <= prev_c_stop < len(c_indices)
            
            prev_c_index = c_indices[prev_c_stop]
            curr_a_to_b = a_n - a_stop
            if 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:
                while 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
            elif curr_a_to_b_after_c > 0 \
                    and a_indices[a_n - curr_a_to_b_after_c] < prev_c_index:
                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
        
        # saving result
        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


if __name__ == '__main__':
    main()