C2. Рассадка за столами (сложная версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Отличие между версиями заключается в том, что в этой версии ограничения на $$$n$$$, $$$x$$$, $$$s$$$, $$$t$$$ выше. Вы можете делать взломы только в том случае, если решили все версии этой задачи.

Друзья Алисы пришли на вечеринку и теперь стоят в очереди, чтобы войти.

На вечеринке есть $$$x$$$ столов, за каждым из которых по $$$s$$$ мест. На каждом месте может сидеть только один человек.

У каждого друга есть один из трёх типов личности:

  • интроверты (I) должны сесть за пустой стол;
  • экстраверты (E) должны сесть за непустой стол;
  • амбиверты (A) могут сесть за любой стол.

Изначально все места пусты. Однако, пока Алиса ела тортики, её друзья уже выстроились в очередь, и Алиса не может изменить их порядок. Для каждого человека в очереди Алиса должна либо посадить его за стол, либо выгнать с вечеринки. Каждый человек садится до того, как следующему будет назначен стол.

Алиса хочет, чтобы на вечеринке было как можно веселее, поэтому ей нужно посадить как можно больше людей. Помогите ей найти максимальное число друзей, которых можно оставить на вечеринке.

Обратите внимание, что после того, как друг сел, он не пересаживается и не уходит, даже если позже его место перестанет соответствовать его типу личности.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

В первой строке каждого набора входных данных даны три целых числа $$$n$$$, $$$x$$$ и $$$s$$$ ($$$1 \le n,x,s \le 2\cdot 10^5$$$) — число друзей Алисы, число столов и число мест за каждым столом.

Во второй строке дана строка $$$u$$$ длины $$$n$$$, состоящая только из букв A, E и I, обозначающих соответственно амбиверта, экстраверта и интроверта.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите целое число: максимальное количество людей, которых можно посадить.

Пример
Входные данные
6
5 2 2
EIAIE
20 5 5
AEIEEEEIEAAEIEEEEIEA
8 2 4
AAAAAIEE
8 4 2
AIEAEAAI
8 3 3
AIEAEAAI
4 2 2
IAEE
Выходные данные
4
20
7
7
7
4
Примечание

В первом наборе входных данных есть $$$2$$$ стола по $$$2$$$ места за каждым. Вот один из способов посадить максимальное количество людей:

Первый человек — экстраверт. Поскольку все столы пусты, ему приходится уйти с вечеринки.

Второй человек — интроверт. Алиса может посадить его за первый стол, который пуст.

Третий человек — амбиверт. Алиса может посадить его за первый стол.

Четвёртый человек — интроверт. Алиса может посадить его за второй стол, который пуст.

Пятый человек — экстраверт. Алиса может посадить его за второй стол, который не пуст.

Таким образом, на вечеринке сидят четыре человека. Это максимально возможное число, поскольку на вечеринке всего четыре места.