P13486 [GCJ 2008 Finals] Juice

你正在举办一场派对。为此，你正在通过混合三种不同类型的果汁来制作饮品：苹果汁、香蕉汁和胡萝卜汁。我们将这三种果汁分别记作 $A$、$B$ 和 $C$。 你希望决定饮品中每种果汁所占的比例，使得能让尽可能多的参加派对的人喜欢这款饮品。 每个人对于饮品中每种果汁都有一个最小比例的要求。只有当饮品中每种果汁的比例都大于等于他所要求的最小比例时，他才会喜欢这款饮品。 请你计算，最多能让多少人喜欢你调制的饮品。

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

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

**提示** 在第一个样例中，对于每种果汁，都有一个人希望饮品完全由该果汁组成！显然你只能满足其中一个人的要求。 在第二个样例中，你可以满足三个人中的任意两个人的要求。 在第三个样例中，如果你将三种果汁等分混合，五个人都会喜欢这款饮品。 **数据范围** - $1 \leq T \leq 12$ **小数据集（测试集 1 - 可见）** - $1 \leq N \leq 10$ **大数据集（测试集 2 - 隐藏）** - $1 \leq N \leq 5000$ 由 ChatGPT 4.1 翻译