2495. Juice

单点时限: 2.0 sec

内存限制: 256 MB

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

输入格式

One line containing an integer T(1 ≤ T ≤ 12 ), the number of test cases in the input file.

For each test case, there will be:

  • One line containing the integer N(1 ≤ N ≤ 5000 ), 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 ≤ 10000.

输出格式

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.

样例

Input
3
3
10000 0 0
0 10000 0
0 0 10000
3
5000 0 0
0 2000 0
0 0 4000
5
0 1250 0
3000 0 3000
1000 1000 1000
2000 1000 2000
1000 3000 2000
Output
Case #1: 1
Case #2: 2
Case #3: 5
Hint:
In the first case, for each juice, we have one person that wants the drink to be made entirely out of that juice! Clearly we can only satisfy one of them.
In the second case, we can satisfy any two of the three preferences.
In the third case, all five people will like the drink if we make it using equal thirds of each juice.

0 人解决,0 人已尝试。

0 份提交通过,共有 0 份提交。

9.9 EMB 奖励。

创建: 15 年,3 月前.

修改: 6 年,9 月前.

最后提交: N/A.

来源: GCJ 2008

题目标签