Вам задано две строки \(s\) и \(t\), состоящие из строчных букв латинского алфавита. Длина \(t\) равна \(2\) (то есть эта строка состоит ровно из двух символов).
За один ход вы можете выбрать любой символ \(s\) и заменить его на любую строчную букву латинского алфавита. Более формально, вы выбираете какое-то \(i\) и заменяете \(s_i\) (символ на позиции \(i\)) на какой-то символ от 'a' до 'z'.
Вы хотите сделать не более \(k\) замен таким образом, чтобы максимизировать количество вхождений \(t\) в \(s\) в качестве подпоследовательности.
Напомним, что подпоследовательность — это последовательность, которая может быть получена из заданной последовательности путем удаления нуля или более элементов без изменения порядка остальных элементов.
Первая строка входных данных содержит два целых числа \(n\) и \(k\) (\(2 \le n \le 200\); \(0 \le k \le n\)) — длина \(s\) и максимальное количество ходов, которое можно сделать. Вторая строка входных данных содержит строку \(s\), состоящую из \(n\) строчных букв латинского алфавита. Третья строка входных данных содержит строку \(t\), состоящую из двух строчных букв латинского алфавита.
Выведите одно целое число — максимально возможное количество вхождений \(t\) в \(s\) в качестве подпоследовательности при оптимальной замене не более \(k\) символов в \(s\).
В первом примере можно получить строку «abab», заменив \(s_1\) на 'a' и \(s_4\) на 'b'. Тогда ответ будет равен \(3\).
Во втором примере можно получить строку «ssddsdd» и получить ответ \(10\).
В четвертом примере можно получить строку «aaacaaa» и получить ответ \(15\).
4 2 bbaa ab
3
7 3 asddsaf sd
10
15 6 qwertyhgfdsazxc qa
16
7 2 abacaba aa
15
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач