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