This page is still under construction.

Parts of this page are still being built. What you see may change.

Civilization

Time limit1sMemory limit256 MB

Summary
Pick the smallest subset of at most 18 regions whose total workforce, tax income, and farm count all reach the required thresholds, or print game over.
Level

Medium4 of 10

Topics
Brute force, Bit manipulation
Solved
No attempts yet

Problem

Emperor Montezuma of the Aztec civilization has a hard time planning the output of his capital city. The city is divided into square regions of equal size, and each region has three important values: the workforce, meaning the number of people able to work, the tax income Montezuma collects from the region, given in Quetzal, the Aztec currency, and the number of farms.

A region contributes to the city only if an administrator is assigned to it. A region without an administrator stays self sufficient and is not counted as part of the city. Montezuma collects no taxes there, cannot use its workforce, and cannot use the food its farms produce.

Montezuma wants his capital to be prosperous while using as few administrators as possible. The city is prosperous when the total workforce, the total tax income and the total number of farms over the administered regions are each at least the given threshold.

Montezuma had no computer. You read about him in the encyclopedia of the computer game Civilization, so you decided to write a program that computes the fewest regions Montezuma has to administer for the city to reach the workforce, tax and farm thresholds at the same time.

Input

The first line contains the number of test cases TT.

The first line of each test case contains the number of regions near the capital, NN. The next line contains the workforce WW, the tax income CC and the number of farms FF that the city needs to be prosperous, separated by spaces. Each of the next NN lines contains the workforce wiw_i, the tax income cic_i and the number of farms fif_i that region ii offers.

  • 0<T≤1000 < T \le 100
  • 0<N≤180 < N \le 18
  • 0<W,C,F≤10000 < W, C, F \le 1000
  • 0<wi,ci,fi≤10000 < w_i, c_i, f_i \le 1000

Output

For each test case, print on one line the minimum number of regions that need an administrator. If no choice of regions makes the city prosperous, print game over instead.

Examples3

  1. Example 1

    Input
    2
3
50 50 50
10 20 30
40 30 22
10 10 33
2
10 20 30
5 5 5
200 10 20
    Expected output
    2
game over

  2. Example 2

    Input
    1
1
1 1 1
1 1 1
    Expected output
    1

  3. Example 3

    Input
    1
1
1000 1000 1000
1000 1000 999
    Expected output
    game over