CF2232C2 Seating Arrangement (Hard Version)

这是该题目的 Hard 版本。与其它版本的区别在于本版本中 $n$、$x$、$s$、$t$ 的约束范围更大。只有解决了所有版本后才可以进行 Hack。 Alice 的朋友们来到派对，现在他们正排队准备进入派对。 派对上有 $x$ 张桌子，每张桌子有 $s$ 个座位。每个座位只能坐一个人。 每位朋友有以下三种性格之一： - 内向型（I）：必须坐在一张空桌子上。 - 外向型（E）：必须坐在一张非空桌子上。 - 两性型（A）：可以坐在任何桌子上。 最开始，所有座位都是空的。然而，由于 Alice 在吃蛋糕，她的朋友们已经排好队了，Alice 不能更改他们的顺序。对于队伍中的每个人，Alice 必须为他分配桌子或将其请出派对。每个人都在下一个人被分配桌子之前就已经就座。 为了让派对更加有趣，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$。

对于每个测试用例，输出一个整数：能入座的最大人数。

在第一个测试用例中，有 $2$ 张桌子，每张桌子有 $2$ 个座位。以下是一种使入座人数最多的分配方式： 第一个人是外向型。由于所有桌子都是空的，他只能离开派对。 第二个人是内向型。Alice 可以让他坐在第一张空桌子上。 第三个人是两性型。Alice 可以让他坐在第一张桌子上。 第四个人是内向型。Alice 可以让他坐在第二张空桌子上。 第五个人是外向型。Alice 可以让他坐在第二张非空桌子上。 这样有四个人参加了派对。这是最大值，因为派对上一共有四个座位。 由 ChatGPT 5 翻译