CF2232C1 Seating Arrangement (Easy Version)

这是该问题的 Easy 版本。两个版本的区别在于本版本中 $n$、$x$、$s$、$t$ 的约束更小。只有在你完成了所有版本后才能进行 hack。 Alice 的朋友们来到了派对，现在他们排成一队准备进入派对。 派对上有 $x$ 张桌子，每张桌子有 $s$ 个座位。每个座位只能坐一个人。 每位朋友有以下三种性格之一： - 内向型（I）：必须坐在一个空桌子上； - 外向型（E）：必须坐在一个非空桌子上； - 中间型（A）：可以坐在任何桌子上。 一开始，每个座位都是空的。然而，因为 Alice 正在吃蛋糕，她的朋友们已经排好队了，这个顺序 Alice 无法改变。对于队列中的每个人，Alice 必须给他们分配一个桌子，或者让他们离开派对。每分配好一个人后才能分配下一个人。 为使派对更有趣，Alice 想让尽可能多的朋友参加派对。请你帮她求出最多能让多少个朋友参加派对。 注意：一旦一个人就座后，即使后来不再符合其性格限制，也不能再移动。

每个测试包含多组测试数据。第一行为测试组数 $t$（$1 \leq t \leq 500$）。接下来是每组测试数据的描述。 每组测试的第一行包含三个整数 $n$、$x$、$s$（$1 \leq n, x, s \leq 3000$），分别表示 Alice 的朋友数、桌子数和每张桌子的座位数。第二行为一个长度为 $n$ 的字符串 $u$，只包含字母 A、E、I，分别代表中间型、外向型和内向型。 保证所有测试中 $n$ 的总和不超过 $3000$。

对于每组测试数据，输出一个整数，表示最多能就座的人数。

在第一个测试中，有 $2$ 张桌子，每张桌子有 $2$ 个座位。下面是实现最多就座人数的一种方案： 第一个人是外向型，由于所有桌子都是空的，他得离开。 第二个人是内向型，Alice 可将他安排到第一张空桌。 第三个人是中间型，Alice 可将他安排到第一张桌子。 第四个人是内向型，Alice 可将他安排到第二张空桌。 第五个人是外向型，Alice 可将他安排到第二张非空桌。 因此共 $4$ 个人坐在了派对上。这已经是最大值，因为派对上只有 $4$ 个座位。 由 ChatGPT 5 翻译