Задана полоска из $$$n$$$ ячеек, все ячейки изначально покрашены в красный цвет.
За одну операцию можно выбрать отрезок подряд идущих ячеек и покрасить их в синий цвет. До покраски выбранные ячейки могут быть как красные, так и синие. Обратите внимание, что в красный цвет красить невозможно. Всего разрешается применить не более $$$k$$$ операций (возможно ноль).
Для каждой ячейки задано, какого цвета она должна быть после выполнения всех операций: красная или синяя.
Очевидно, не всегда можно за $$$k$$$ операций удовлетворить все требования. Поэтому для каждой ячейки также указан штраф, который применяется, если ячейка оказывается неправильного цвета после применения всех операций. Для $$$i$$$-й ячейки штраф равен $$$a_i$$$.
Штраф итоговой покраски считается как максимальный штраф по всем ячейкам, которые покрашены в неправильный цвет. Если таких ячеек нет, то штраф покраски равен $$$0$$$.
Какой наименьший штраф итоговой покраски можно получить?
В первой строке записано одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
В первой строке каждого набора входных данных записаны два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 3 \cdot 10^5$$$; $$$0 \le k \le n$$$) — длина полоски и максимальное количество операций.
Во второй строке записана строка $$$s$$$, состоящая из $$$n$$$ символов 'R' и/или 'B'. 'R' означает, что ячейка должна быть покрашена в красный цвет. 'B' означает, что ячейка должна быть покрашена в синий цвет.
В третьей строке записаны $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — штраф за каждую ячейку.
Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$3 \cdot 10^5$$$.
На каждый набор входных данных выведите одно целое число — наименьший штраф итоговой покраски.
54 1BRBR9 3 5 44 1BRBR9 5 3 44 2BRBR9 3 5 410 2BRBRBBRRBR5 1 2 4 5 3 6 1 5 45 5RRRRR5 3 1 2 4
3 3 0 4 0
В первом наборе входных данных можно покрасить ячейки с $$$1$$$ по $$$3$$$. Покраска будет BBBR. То есть, только ячейка $$$2$$$ покрашена в неправильный цвет. Значит штраф за нее и есть итоговый штраф и равен $$$3$$$.
Во втором наборе покраска BBBR теперь даст штраф $$$5$$$. А если покрасить ячейки с $$$1$$$ по $$$1$$$, получив BRRR, то только ячейка $$$3$$$ покрашена в неправильный цвет. Итоговый штраф равен $$$3$$$.
В третьем наборе можно покрасить ячейки с $$$1$$$ по $$$1$$$ и с $$$3$$$ по $$$3$$$. Тогда все ячейки будут правильного цвета — штраф равен $$$0$$$.
