반격

Joshua와 Rasmus는 카드 게임을 하고 있다. 원래의 카드 게임을 알아보더라도, 규칙을 주의 깊게 읽어야 한다. Joshua의 체력은 $H_J$이고 Rasmus의 체력은 $H_R$이다.

Rasmus는 전장에 $N$마리의 생물을 가지고 있으며, 각 생물에는 주어진 공격력이 있다. Joshua도 전장에 $M$마리의 생물을 가지고 있으며, 각 생물에는 마찬가지로 주어진 공격력이 있다.

모든 생물은 다음 능력을 가진다.

• 치명타: 다른 생물을 방어하거나 다른 생물에게 방어당한 생물은 모두 파괴된다.

• 생명연결 (생명연결은 일반적으로 생물이 피해를 줄 때마다 그 조종자의 체력을 회복시키지만, 이 게임에서는 플레이어를 공격할 때만 작동한다.): 이 생물이 플레이어에게 전투 피해를 줄 때마다, 그 조종자는 그 피해량만큼 생명력을 얻는다.

공격력이 $0$인 모든 생물을 벽이라고 부른다. Rasmus가 가진 벽의 수를 $K$라 하자. Rasmus의 차례이며, 그는 벽이 아닌 자신의 모든 생물로 Joshua를 공격한다.

공격받은 플레이어는 자신의 생물로 방어할 수 있다. 각 생물은 최대 하나의 공격 생물만 방어할 수 있고, 각 공격 생물은 최대 하나의 생물에게만 방어당할 수 있다. 공격 생물이 방어당했는지에 따라 다음 두 가지 중 하나가 일어난다.

• 방어당함: 공격 생물은 공격받은 플레이어에게 $0$의 피해를 주고, 공격 생물과 방어 생물이 모두 파괴된다.

• 방어당하지 않음: 공격 생물은 자신의 공격력만큼 공격받은 플레이어에게 피해를 주고, 공격하는 플레이어의 체력을 같은 양만큼 회복시킨다.

생물은 공격한 뒤 지쳐서 다음 차례에 방어할 수 없다.

Joshua는 Rasmus의 공격을 어떻게 방어할지 선택해야 한다. Rasmus의 공격이 끝난 뒤 Joshua의 체력이 $\leq 0$이면 즉시 패배한다. Joshua가 살아남으면, 살아남은 자신의 모든 생물로 반격한다.

그러면 Rasmus는 Joshua의 반격에 대응한다. 그는 자신의 벽 $K$개를 사용해 Joshua가 공격하는 생물 중 공격력이 가장 높은 생물을 최대 $K$마리까지 가능한 한 많이 방어한다. (Rasmus의 공격 생물들은 너무 지쳐서 방어할 수 없다.) 방어당한 생물은 $0$의 피해를 주고, 방어당하지 않은 나머지 모든 생물은 자신의 공격력만큼 Rasmus에게 피해를 준다.

Joshua가 방어 생물을 배정하여 그 차례에 살아남은 뒤 반격으로 Rasmus의 체력을 $\leq 0$까지 줄일 수 있는지 판별한다.

채점

당신의 해답은 여러 테스트 그룹으로 이루어진 테스트 세트에서 검사된다. 한 그룹의 점수를 얻으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 점수 | 제약 조건

$1$ |$10$| $H_J, H_R, M, N \leq 10$이고 모든 $B_j, A_i \leq 10$.

$2$ |$30$| $M, N \leq 2000$

$3$ |$15$| 벽이 아닌 모든 생물의 공격력은 $1$이다.

$4$ |$15$| $K = 0$ (Rasmus에게 벽이 없다).

$5$ |$30$| 추가 제약 조건 없음.

입력의 첫째 줄에는 네 정수 $H_J$, $H_R$, $M$, $N$ ($1 \leq H_J, H_R \leq 10^9$, $1 \leq N, M \leq 10^5$)가 주어진다.

다음 줄에는 Joshua의 생물들의 공격력을 나타내는 $M$개의 정수 $B_1, B_2, \dots, B_M$ ($1 \leq B_j \leq 10^9$)가 주어진다.

셋째 줄에는 Rasmus의 생물들의 공격력을 나타내는 $N$개의 정수 $A_1, A_2, \dots, A_N$ ($0 \leq A_i \leq 10^9$)가 주어진다.

Joshua가 살아남아 반격으로 승리할 수 있으면 YES`''를 출력하고, 그렇지 않으면 NO`''를 출력한다.

Joshua와 Rasmus의 체력은 각각 $10$이다. Rasmus는 공격력이 $5$인 생물 하나로 공격한다(다른 하나는 벽이다). Joshua가 공격력이 $5$인 공격 생물을 방어하면, 공격력이 $3$인 생물 $1$마리가 남는다. Rasmus의 벽이 이 생물을 방어하므로 Joshua는 $0$의 피해를 준다. Rasmus의 체력은 여전히 $10$이다. Joshua가 방어하지 않으면 $5$의 피해를 받고(체력은 $5$가 된다), Rasmus는 $5$만큼 회복한다(체력은 $15$가 된다). 그런 다음 Joshua는 공격력이 $3$인 생물 두 마리로 반격한다. Rasmus의 벽이 그중 하나를 방어하고, 다른 하나가 $3$의 피해를 준다. 마지막에 Rasmus의 체력은 $12$이다. 두 경우 모두 Joshua는 이길 수 없다.

Joshua의 체력은 $10$이고 Rasmus의 체력은 $5$이다. Joshua는 다음과 같이 이길 수 있다. Rasmus는 공격력이 $5$인 생물 하나로 공격한다. Joshua는 공격력이 $5$인 자신의 생물 세 마리 중 하나로 그 생물을 방어한다. Joshua는 체력 $10$으로 살아남고, 공격력이 $5$인 생물 두 마리가 남는다. Rasmus의 벽이 그중 하나를 방어하고, 다른 하나가 Rasmus에게 $5$의 피해를 준다. Rasmus의 체력은 $5 - 5 = 0$이 된다. Joshua가 승리한다!

Joshua와 Rasmus의 체력은 각각 $5$이다. Rasmus는 공격력이 $10$인 생물 하나로 공격한다. Joshua가 공격력이 $20$인 자신의 생물로 그 생물을 방어하면, 반격에 사용할 생물이 하나도 남지 않는다. Rasmus의 체력은 여전히 $5$이다. Joshua가 방어하지 않으면 $10$의 피해를 받고 즉시 패배한다. 어느 경우에도 Joshua는 이길 수 없다.