题目描述

你在一个动物收容所工作，负责喂养动物。你已经准备了 $D$ 份狗粮和 $C$ 份猫粮。

总共有 $N$ 只动物在排队，其中一些是狗，另一些是猫。也可能所有动物都是狗或都是猫。一个长度为 $N$ 的字符串 $S$，由字符 C 和 D 组成，表示队伍中猫和狗的顺序。如果队伍中的第 $i$ 只动物是猫，则第 $i$ 个字符为 C；如果是狗，则为 D。

动物按照它们在队伍中的顺序进食。每只狗恰好吃掉 $1$ 份狗粮，同样每只猫恰好吃掉 $1$ 份猫粮。此外，你还有额外的猫粮。每当一只狗吃完食物后，你会为猫带来 $M$ 份额外的猫粮。

动物必须按照它们在队伍中的顺序进食，并且只有当它前面的动物已经吃完后，它才能进食。这意味着，如果你用完了狗粮（或猫粮），而将要喂食的是一只狗（或猫），那么队伍将不会前进，所有动物都会耐心等待。

你需要判断在这种情况下，队伍中所有的狗是否都能被喂饱。注意，这意味着某些猫可能会留在队伍中，但不用担心，你稍后会喂它们！

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。

每个测试用例的第一行包含四个整数 $N$、$D$、$C$ 和 $M$：分别表示动物的数量、初始的狗粮份数、初始的猫粮份数，以及在一只狗吃掉一份狗粮后额外添加的猫粮份数。

下一行包含一个长度为 $N$ 的字符串 $S$，表示动物的排列。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 为 YES（如果所有狗都能被喂饱）或 NO（否则）。

3
6 10 4 0
CCDCDD
4 1 2 0
CCCC
4 2 1 0
DCCD

Case #1: YES
Case #2: YES
Case #3: NO

2
12 4 2 2
CDCCCDCCDCDC
8 2 1 3
DCCCCCDC

Case #1: YES
Case #2: NO

提示

在样例 #1 中，有 $10$ 份狗粮和 $4$ 份猫粮。

• 前 $2$ 只动物是猫，它们吃完后，剩下 $2$ 份猫粮。
• 然后一只狗吃掉 $1$ 份狗粮，此时剩下 $9$ 份狗粮。
• 接下来一只猫吃掉 $1$ 份猫粮，猫粮剩余 $1$ 份。
• 最后 $2$ 只动物是狗，它们各吃掉 $1$ 份狗粮。

因此，在这个例子中，所有狗都能吃到食物。

在样例 #2 中，没有狗。因此，所有（$0$ 只）狗当然都能被喂饱。

在样例 #3 中，第二只狗前面的猫无法吃到食物，因为猫粮不够。因此，第二只狗也无法吃到食物。

限制条件

$1 \le T \le 100$。

$1 \le N \le 10^4$。

$0 \le D, C \le 10^6$。

$S$ 仅由字符 C 和 D 组成。

测试集 1

$M = 0$。

测试集 2

$0 \le M \le 10^6$。

翻译由 DeepSeek V4 Pro 完成