题目描述

这是本题的简单版本，区别在于 $n,x,s$ 的限制更小。只有解决了所有版本后才能 hack。

Alice 的朋友们排队进入派对。派对上有 $x$ 张桌子，每张桌子有 $s$ 个座位，每个座位最多坐一个人。

每个朋友有三种性格之一：

• 内向者 I：只能坐在空桌子旁；
• 外向者 E：只能坐在非空桌子旁；
• 双向者 A：可以坐在任意桌子旁。

一开始所有座位都是空的。朋友们的顺序已经固定，Alice 不能改变他们的顺序。对队伍中的每个人，Alice 必须立刻决定给他安排一张桌子，或让他离开派对；安排完当前人后才会处理下一个人。

已坐下的人之后不会移动，即使后来桌子的状态不再符合他的性格限制。

请你求出最多能让多少人入座。

输入格式

第一行包含一个整数 $t$，表示测试组数。

每组测试数据第一行包含三个整数 $n,x,s$，分别表示朋友数量、桌子数量、每张桌子的座位数。

第二行包含一个长度为 $n$ 的字符串 $u$，仅由 A、E、I 组成，表示每个人的性格。

输出格式

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

数据范围

• $1 \le t \le 500$
• $1 \le n,x,s \le 3000$
• 所有测试数据的 $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$ 个座位。下面是实现最多座位数的方法之一。

第一个人是外向型。由于所有桌子都空着，他们必须离开聚会。

第二个人性格内向。爱丽丝可以把他们分配到第一张空桌。

第三个人性格内向。爱丽丝可以将他们分配到第一张桌子。

第四个人性格内向。爱丽丝可以把他们分配到第二张空桌。

第五个人性格外向。爱丽丝可以把他们分配到第二张桌子，这张桌不是空的。

这样，聚会上就有四个座位。这是最大值，因为聚会上只有四个座位。

来源

Codeforces Round 2232 C1 - Seating Arrangement (Easy Version)