개와 고양이

당신은 동물 보호소에서 일하며 동물들에게 먹이를 주는 일을 담당한다. 이미 개 사료 $\mathbf{D}$인분과 고양이 사료 $\mathbf{C}$인분을 준비했다.

줄에는 총 $\mathbf{N}$마리의 동물이 기다리고 있으며, 일부는 개이고 나머지는 고양이이다. 줄에 있는 동물이 모두 개이거나 모두 고양이일 수도 있다. C와 D 문자로 이루어진 길이 $\mathbf{N}$의 문자열 $\mathbf{S}$는 줄에 선 고양이와 개의 순서를 나타낸다. 줄의 $i$번째 동물이 고양이라면 $i$번째 문자는 C와 같다. 마찬가지로, 줄의 $i$번째 동물이 개라면 $i$번째 문자는 D와 같다.

동물들은 줄에 서 있는 순서대로 먹이를 먹는다. 각 개는 정확히 개 사료 $1$인분을 먹고, 마찬가지로 각 고양이는 정확히 고양이 사료 $1$인분을 먹는다. 또한 여분의 고양이 사료가 있다. 개가 사료를 먹을 때마다 고양이들을 위해 고양이 사료 $\mathbf{M}$인분을 추가로 가져온다.

동물들은 줄에서 기다리는 순서대로 먹이를 먹어야 하며, 어떤 동물은 바로 앞의 동물이 이미 먹은 경우에만 먹을 수 있다. 이는 개 사료나 고양이 사료가 떨어진 상태에서 각각 개나 고양이가 먹을 차례가 되면 모든 동물이 참을성 있게 기다리므로 줄이 더 이상 움직이지 않는다는 뜻이다.

이 상황에서 줄에 있는 모든 개가 먹이를 먹게 되는지 판별해야 한다. 이는 일부 고양이가 줄에 남을 수도 있다는 뜻이지만, 걱정하지 않아도 된다. 그 고양이들에게는 나중에 결국 먹이를 줄 것이다!

제한

메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$. $1 \le \mathbf{N} \le 10^4$. $0 \le \mathbf{D}, \mathbf{C} \le 10^6$. $\mathbf{S}$는 C와 D 문자로만 이루어진다.

테스트 세트 1

시간 제한: 20초. $\mathbf{M} = 0$

테스트 세트 2

시간 제한: 40초. $0 \le \mathbf{M} \le 10^6$.

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 네 정수 $\mathbf{N}$, $\mathbf{D}$, $\mathbf{C}$, $\mathbf{M}$가 주어진다. 각각 동물의 수, 처음에 있는 개 사료의 인분 수, 처음에 있는 고양이 사료의 인분 수, 그리고 개가 개 사료 한 인분을 먹은 뒤 추가하는 고양이 사료의 인분 수를 나타낸다.

다음 줄에는 동물의 배치를 나타내는 길이 $\mathbf{N}$의 문자열 $\mathbf{S}$가 주어진다.

각 테스트 케이스마다 Case #$x$: $y$를 포함하는 한 줄을 출력한다. 여기서 $x$는 $1$부터 시작하는 테스트 케이스 번호이고, $y$는 모든 개가 먹이를 먹게 된다면 YES, 그렇지 않다면 NO이다.

예제 케이스 #1에서는 개 사료가 $10$인분, 고양이 사료가 $4$인분 있다.

• 처음 두 동물은 고양이이므로, 이들이 먹고 나면 고양이 사료가 $2$인분 남는다.

• 그다음 개 한 마리가 개 사료 한 인분을 먹는다. 이제 개 사료가 $9$인분 남는다.

• 다음으로 고양이 한 마리가 고양이 사료 한 인분을 먹어, 고양이 사료의 인분 수가 $1$로 줄어든다.

• 마지막 두 동물은 개이며, 각각 개 사료 한 인분을 먹는다.

따라서 이 경우에는 모든 개가 먹을 수 있다.

예제 케이스 #2에는 개가 없다. 따라서 모든 개, 즉 한 마리도 없는 개가 자명하게 먹을 수 있다.

예제 케이스 #3에서는 두 번째 개 앞에 있는 고양이가 고양이 사료의 인분 수가 충분하지 않아 먹을 수 없다. 따라서 두 번째 개도 먹지 못한다.

추가 예제 - 테스트 세트 2

예제 케이스 #1에서는 개가 개 사료 한 인분을 먹을 때마다 고양이 사료 $2$인분이 생긴다.

• 첫 번째 고양이가 먹고 나면 고양이 사료가 $1$인분 남는다.

• 그다음 개 한 마리가 먹고 나면 개 사료가 $3$인분, 고양이 사료가 $3$인분 남는다.

• 다음 $3$마리의 고양이가 먹고 나면 개 사료가 $3$인분, 고양이 사료가 $0$인분 남는다.

• 그다음 개 한 마리가 먹고 나면 개 사료가 $2$인분, 고양이 사료가 $2$인분 남는다.

• 다음 $2$마리의 고양이가 먹이를 먹고 나면 개 사료가 $2$인분, 고양이 사료가 $0$인분 남는다.

• 이제 개 한 마리가 먹고 나면 개 사료가 $1$인분, 고양이 사료가 $2$인분 남는다.

• 다음으로 고양이 한 마리가 먹고 나면 개 사료가 $1$인분, 고양이 사료가 $1$인분 남는다.

• 마지막 개가 남은 개 사료 한 인분을 먹는다.

따라서 이 경우에는 모든 개가 먹을 수 있다.

예제 케이스 #2에서는 두 번째 개 앞에 있는 고양이가 고양이 사료의 인분 수가 충분하지 않아 먹을 수 없다.