병사 선발 (작은 입력)

시간 제한5초메모리 제한512 MB

요약

지금까지 고른 병사보다 공격력이나 방어력이 큰 병사를 두 사람이 번갈아 고를 때, 선공이 더 많은 병사를 가져가도록 보장할 수 있는지 판정한다.

문제

앨리스 장군과 밥 장군이 병사 $N$ 명으로 전쟁 게임을 한다. $i$ 번 병사의 공격력은 $A_i$ , 방어력은 $D_i$ 이다.

게임을 시작하기 전에 두 장군은 번갈아 병사를 뽑고, 앨리스가 먼저 뽑는다. 지금까지 뽑힌 병사의 집합을 $S$ 라고 하자. 차례가 된 장군은 다음 두 조건 중 적어도 하나를 만족하는 병사 $x$ 를 뽑을 수 있다.

$S$ 가 비어 있는 동안에는 두 조건이 모두 성립하므로 첫 병사는 아무나 뽑아도 된다. 이미 $S$ 에 있는 병사는 자기 공격력과 방어력을 넘지 못하므로 다시 뽑을 수 없다. 차례가 된 장군이 뽑을 병사가 하나도 없으면 선발이 끝나고 게임이 시작된다.

앨리스는 밥보다 병사를 많이 뽑으려 하고, 밥은 이를 막으려 한다. 두 장군이 각자의 목표에 맞춰 최선을 다할 때 앨리스가 목표를 이루는지 판정하라.

첫 줄에 테스트 케이스의 수 $T$ 가 주어진다. 각 테스트 케이스의 첫 줄에는 병사의 수 $N$ 이 주어지고, 이어지는 $N$ 개 줄에는 $i$ 번 병사의 공격력 $A_i$ 와 방어력 $D_i$ 가 공백으로 구분되어 주어진다.

제한:

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 밥이 어떻게 하더라도 앨리스가 더 많은 병사를 뽑을 수 있으면 YES, 그렇지 않으면 NO이다.

예제 1

입력

예상 출력

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