← 返回题目列表

Codeforces · 2232/C1

C1. 座位安排(简易版)

中文机器翻译题面 查看原题

这是问题的简单版本。版本之间的区别在于,在这个版本中,$$$n$$$、$$$x$$$、$$$s$$$、$$$t$$$ 的约束较小。只有解决了该问题的所有版本,您才能破解。

Alice的朋友们来参​​加聚会了,现在他们正在排队进入聚会。

聚会上有 $$$x$$$ 张桌子,每张桌子都有 $$$s$$$ 个座位。每个座位只能容纳一个人。

每个朋友都具有以下三种性格之一:

  • 内向者 (I) 必须坐在空桌子旁的人
  • 外向者 (E) 必须坐在非空桌子旁的人
  • 中间性格 (A) 可以坐在任何桌子上。

最初,每个座位都是空的。然而,由于爱丽丝正在吃蛋糕,她的朋友们已经排好了队,爱丽丝无法改变他们的顺序。对于队列中的每个人,爱丽丝必须为他们分配一张桌子或将他们踢出队伍。每个人就座后,下一个人就被分配到一张桌子。

Alice 想要在聚会上玩得开心,她需要在聚会上容纳尽可能多的人。帮助她找到参加聚会的最多朋友数量。

注意,一旦好友入座,即使不再按照其性格入座,也不允许再移动。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 500$$$)。测试用例的描述如下。

每个测试用例的第一行包含三个整数 $$$n$$$、$$$x$$$ 和 $$$s$$$ ($$$1 \le n,x,s \le 3000$$$) – Alice 的朋友数量、桌子数量以及每张桌子的座位数量。第二行包含长度为 $$$n$$$ 的字符串 $$$u$$$,仅包含字母 A, E,和 I,分别代表中间性格、外向和内向。

保证所有测试用例的$$$n$$$总和最多为$$$3000$$$。

输出

对于每个测试用例,输出一个整数:最大就座人数。

示例

输入
复制

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$$$ 座位。这是实现最大就座人数的方法之一。

第一个人是一个外向的人。由于所有桌子都空了,他们不得不离开聚会。

第二个人是一个内向的人。 Alice 可以将它们分配给第一个表,该表是空的。

第三个人是一个中间性格者。 Alice 可以将它们分配到第一个表。

第四个人是一个内向的人。 Alice 可以将它们分配给第二个表,该表是空的。

第五个人是一个外向的人。 Alice 可以将它们分配给第二个表,该表不为空。

因此,聚会上坐了四个人。这是最大的,因为聚会上只有四个座位。