문명

아즈텍 문명의 황제 몬테수마는 수도의 생산 계획을 세우느라 애를 먹고 있다. 수도는 크기가 같은 정사각형 구역으로 나뉘어 있고, 각 구역에는 중요한 값이 세 가지 있다. 일할 수 있는 사람의 수인 노동력, 몬테수마가 그 구역에서 걷는 세금(아즈텍 화폐 케찰로 주어진다), 그리고 농장의 개수다.

구역이 수도에 기여하려면 행정관 한 명을 배치해야 한다. 행정관이 없는 구역은 자급자족 상태로 남아 수도의 일부로 인정되지 않는다. 몬테수마는 그런 구역에서 세금을 걷지 못하고, 노동력도 쓰지 못하고, 농장에서 나온 식량도 쓰지 못한다.

몬테수마는 수도를 충분히 번영하게 만들고 싶지만 행정관은 최대한 적게 쓰려고 한다. 행정관을 배치한 구역의 노동력 합, 세금 합, 농장 수 합이 각각 주어진 기준값 이상이면 수도는 번영한다.

몬테수마의 시대에는 컴퓨터가 없었다. 당신은 컴퓨터 게임 문명의 백과사전에서 몬테수마의 이야기를 읽고, 수도가 노동력과 세금과 농장 기준을 모두 넘기도록 만들려면 행정관을 배치할 구역이 최소 몇 개 필요한지 계산하는 프로그램을 작성하기로 했다.

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

각 테스트 케이스의 첫째 줄에는 수도 주변 구역의 개수 $N$이 주어진다. 다음 줄에는 수도가 번영하려면 필요한 노동력 $W$, 세금 $C$, 농장 수 $F$가 공백으로 구분되어 주어진다. 이어지는 $N$개의 줄에는 $i$번 구역이 제공하는 노동력 $w_i$, 세금 $c_i$, 농장 수 $f_i$가 주어진다.

• $0 < T \le 100$
• $0 < N \le 18$
• $0 < W, C, F \le 1000$
• $0 < w_i, c_i, f_i \le 1000$

각 테스트 케이스마다 행정관을 배치해야 하는 구역의 최소 개수를 한 줄에 출력한다. 어떤 구역을 골라도 수도가 번영할 수 없으면 그 자리에 game over를 출력한다.