Description

你正在举办一场派对。为此，你正在通过混合三种不同类型的果汁来制作饮品：苹果汁、香蕉汁和胡萝卜汁。我们将这三种果汁分别记作 $A$、$B$ 和 $C$。

你希望决定饮品中每种果汁所占的比例，使得能让尽可能多的参加派对的人喜欢这款饮品。

每个人对于饮品中每种果汁都有一个最小比例的要求。只有当饮品中每种果汁的比例都大于等于他所要求的最小比例时，他才会喜欢这款饮品。

请你计算，最多能让多少人喜欢你调制的饮品。

Input Format

• 第一行包含一个整数 $T$，表示测试用例的数量。

对于每个测试用例，包含：

• 一行一个整数 $N$，表示参加派对的人数。
• 接下来的 $N$ 行，每行包含三个用空格分隔的数字 "$A$ $B$ $C$"，表示每个人对于三种果汁的最小比例要求。$A$、$B$ 和 $C$ 是 $0$ 到 $10000$ 之间的整数，表示以万分之一为单位的比例。保证 $A + B + C \leq 10000$。

Output Format

• 输出 $T$ 行，每行对应一个测试用例，格式为 "Case #$X$: $Y$"，其中 $X$ 是测试用例编号（从 $1$ 开始），$Y$ 是最多能让多少人喜欢你调制的饮品。

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

Case #1: 1
Case #2: 2
Case #3: 5

Hint

提示

在第一个样例中，对于每种果汁，都有一个人希望饮品完全由该果汁组成！显然你只能满足其中一个人的要求。

在第二个样例中，你可以满足三个人中的任意两个人的要求。

在第三个样例中，如果你将三种果汁等分混合，五个人都会喜欢这款饮品。

数据范围

• $1 \leq T \leq 12$

小数据集（测试集 1 - 可见）

• $1 \leq N \leq 10$

大数据集（测试集 2 - 隐藏）

• $1 \leq N \leq 5000$

由 ChatGPT 4.1 翻译