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 $10000$ inclusive, indicating the fraction in parts-per-ten-thousand. $A + B + C \leq 10000$.

You may assume that $1 \leq T \leq 2$ and $1 \leq N \leq 5000$.

-----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.

-----Examples-----
Sample Input:
2
3
10000 0 0
0 10000 0
0 0 10000
3
5000 0 0
0 2000 0
0 0 4000
Sample Output:
Case #1: 1
Case #2: 2

Difficulty: competition

Starter code:

Solutions: