这是问题的困难版本。版本之间的区别在于,在这个版本中,$$$n$$$、$$$x$$$、$$$s$$$、$$$t$$$ 的约束更大。只有解决了该问题的所有版本,您才能破解。
Alice的朋友们来参加聚会了,现在他们正在排队进入聚会。
聚会上有 $$$x$$$ 张桌子,每张桌子都有 $$$s$$$ 个座位。每个座位只能容纳一个人。
每个朋友都具有以下三种性格之一:
- 内向者 (I) 必须坐在空桌子旁的人
- 外向者 (E) 必须坐在非空桌子上的人
- 中间性格 (A) 可以坐在任何桌子上。
最初,每个座位都是空的。然而,由于爱丽丝正在吃蛋糕,她的朋友们已经排好了队,爱丽丝无法改变他们的顺序。对于队列中的每个人,爱丽丝必须为他们分配一张桌子或将他们踢出队伍。每个人就座后,下一个人就被分配到一张桌子。
Alice 想要在聚会上玩得开心,她需要在聚会上容纳尽可能多的人。帮助她找到参加聚会的最多朋友数量。
注意,一旦好友入座,即使不再按照其性格入座,也不允许再移动。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含三个整数 $$$n$$$、$$$x$$$ 和 $$$s$$$ ($$$1 \le n,x,s \le 2\cdot 10^5$$$) – Alice 的朋友数量、桌子数量以及每张桌子的座位数量。第二行包含长度为 $$$n$$$ 的字符串 $$$u$$$,仅包含字母 A, E,和 I,分别代表中间性格、外向和内向。
保证所有测试用例的 $$$n$$$ 总和最多为 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数:最大就座人数。
示例
输入复制
65 2 2EIAIE20 5 5AEIEEEEIEAAEIEEEEIEA8 2 4AAAAAIEE8 4 2AIEAEAAI8 3 3AIEAEAAI4 2 2IAEE
输出复制
4207774
注意
在第一个测试用例中,有 $$$2$$$ 桌子,每张桌子有 $$$2$$$ 座位。这是实现最大就座人数的方法之一。
第一个人是一个外向的人。由于所有桌子都空了,他们不得不离开聚会。
第二个人是一个内向的人。 Alice 可以将它们分配给第一个表,该表是空的。
第三个人是一个中间性格者。 Alice 可以将它们分配到第一个表。
第四个人是一个内向的人。 Alice 可以将它们分配给第二个表,该表是空的。
第五个人是一个外向的人。 Alice 可以将它们分配给第二个表,该表不为空。
因此,聚会上坐了四个人。这是最大的,因为聚会上只有四个座位。