개와 고양이

당신은 동물 보호소에서 동물들에게 먹이를 주는 일을 맡고 있다. 이미 개밥 $D$인분과 고양이밥 $C$인분을 준비해 두었다.

줄을 서서 기다리는 동물은 모두 $N$마리이며, 그중에는 개도 있고 고양이도 있다. 줄에 있는 동물이 전부 개이거나 전부 고양이일 수도 있다. C와 D로 이루어진 길이 $N$의 문자열 $S$가 줄에 있는 고양이와 개의 순서를 나타낸다. 줄에서 $i$번째 동물이 고양이면 $i$번째 문자가 C이고, 개이면 $i$번째 문자가 D이다.

동물들은 줄을 선 순서대로 먹이를 받는다. 개는 개밥을 정확히 $1$인분, 고양이는 고양이밥을 정확히 $1$인분 먹는다. 고양이밥은 여분도 있다. 개가 먹이를 먹을 때마다 고양이를 위해 고양이밥 $M$인분을 추가로 가져온다.

동물들은 줄을 선 순서대로 먹이를 받아야 하고, 자기 앞의 동물이 이미 먹이를 먹어야만 먹이를 먹을 수 있다. 개밥이나 고양이밥이 떨어졌는데 개나 고양이가 먹이를 받으려 한다면 줄은 움직이지 않고, 모든 동물이 참을성 있게 기다린다.

이 상황에서 줄에 있는 개가 모두 먹이를 먹을 수 있는지 판별해야 한다. 고양이 몇 마리가 줄에 남을 수도 있지만, 그 고양이들은 나중에 먹이를 받게 되니 걱정할 필요는 없다.

첫 번째 줄에 테스트 케이스의 수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 네 정수 $N$, $D$, $C$, $M$이 주어진다. 각각 동물의 수, 처음 준비한 개밥 인분 수, 처음 준비한 고양이밥 인분 수, 개가 개밥을 먹은 뒤 추가로 가져오는 고양이밥 인분 수이다.

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

각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력한다. $x$는 테스트 케이스 번호( $1$부터 시작)이고, $y$는 개가 모두 먹이를 먹을 수 있으면 YES, 아니면 NO이다.

• $1 \le T \le 100$.
• $1 \le N \le 10^4$.
• $0 \le D, C \le 10^6$.
• $S$는 C와 D로만 이루어진다.