Problem F
Juice

You are holding a party. In preparation, you are making a drink by mixing together three different types of fruit juice: Apple, Banana, and Carrot. Let’s name the juices A, B and C.

You want to decide what fraction of the drink should be made from each type of juice, in such a way that the maximum possible number of people attending the party like it.

Each person has a minimum fraction of each of the 3 juices they would like to have in the drink. They will only like the drink if the fraction of each of the 3 juices in the drink is greater or equal to their minimum fraction for that juice.

Determine the maximum number of people that you can satisfy.

Input

• One line containing an integer $T$, the number of test cases in the input file.

For each test case, there will be:

• One line containing the integer $N$, the number of people going to the party.

• $N$ lines, one for each person, each containing three space-separated numbers “$A$ $B$ $C$”, indicating the minimum fraction of each juice that would like in the drink. $A$, $B$ and $C$ are integers between $0$ and $10\, 000$ inclusive, indicating the fraction in parts-per-ten-thousand. $A + B + C \leq 10\, 000$.

You may assume that $1 \leq T \leq 2$ and $1 \leq N \leq 5\, 000$.

Output

• $T$ lines, one for each test case in the order they occur in the input file, each containing the string “Case #$X$: $Y$” where $X$ is the number of the test case, starting from 1, and $Y$ is the maximum number of people who will like your drink.

2
3
10000 0 0
0 10000 0
0 0 10000
3
5000 0 0
0 2000 0
0 0 4000

Case #1: 1
Case #2: 2

1
5
0 1250 0
3000 0 3000
1000 1000 1000
2000 1000 2000
1000 3000 2000

Case #1: 5