Description

如今，机器人已经能够驾驶汽车，但它们能举办一场精彩的派对吗？Code Jam 团队对此的研究还处于初级阶段。我们刚刚派遣了 $\mathbf{R}$ 个机器人购物者到本地超市，为我们在多伦多举办的世界总决赛采购派对用品，但它们对加拿大派对的第一印象非常简单：它们只买了 $\mathbf{B}$ 个“bit”（bit 是当地一种小型甜甜圈状点心）。我们以后会继续改进它们的人工智能，但现在，我们希望帮助它们尽快购买完所有的 bit。

超市有 $\mathbf{C}$ 个收银员可以为顾客结账。第 $i$ 个收银员有如下特点：

• 每位顾客最多接受 $\mathbf{M}_{\mathbf{i}}$ 个商品
• 扫描每个商品需要 $\mathbf{S}_{\mathbf{i}}$ 秒
• 还需要额外花费 $\mathbf{P}_{\mathbf{i}}$ 秒用于收款和打包 bit

也就是说，一个顾客如果带着 $\mathrm{N}$ 个 bit 找到第 $i$ 个收银员（其中 $\mathrm{N}$ 必须不超过 $\mathbf{M}_{\mathbf{i}}$），则与该收银员的总交互时间为 $\mathbf{S}_{\mathbf{i}} \times \mathrm{N}+\mathbf{P}_{\mathbf{i}}$ 秒。

在机器人和收银员交互之前，你可以任意分配 bit 给机器人（bit 必须保持完整，不能拆分成小数部分！）。任何没有分到 bit 的机器人将无法与收银员交互，并会失望地离开。

接下来，对于每个至少分到一个 bit 的机器人，你需要为其选择一个不同的收银员。（两个机器人不能使用同一个收银员，一个机器人也不能使用多个收银员。）所有机器人会在时间 0 同时开始与各自的收银员交互。注意，一旦某个机器人完成了与收银员的交互，它不能再获得更多 bit，也不能与其他收银员交互。

如果你帮助机器人做出最优选择，所有机器人最早能在什么时候全部完成与收银员的交互？

Input Format

输入的第一行包含一个整数 $\mathbf{T}$，表示测试用例的数量。接下来有 $\mathbf{T}$ 个测试用例。每个测试用例的第一行包含三个整数 $\mathbf{R}, \mathbf{B}, \mathbf{C}$，分别表示机器人数量、bit 数量和收银员数量。接下来的 $\mathbf{C}$ 行，每行包含三个整数 $\mathbf{M}_{\mathbf{i}}, \mathbf{S}_{\mathbf{i}}, \mathbf{P}_{\mathbf{i}}$，分别表示第 $i$ 个收银员能处理的最大 bit 数、每个 bit 的扫描时间（秒）以及收款和打包时间（秒），如上所述。

Output Format

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是所有机器人最早能完成与收银员交互的时间（单位为秒）。

3
2 2 2
1 2 3
1 1 2
2 2 2
1 2 3
2 1 2
3 4 5
2 3 3
2 1 5
2 4 2
2 2 4
2 5 1

Case #1: 5
Case #2: 4
Case #3: 7

Hint

样例解释

在样例 1 中，有两个机器人、两个 bit 和两个收银员，每个收银员最多只能处理一个商品。因此，必须给每个机器人分配一个 bit。收银员 1 需要 5 秒，收银员 2 需要 3 秒，所以所需时间为 5 秒。

样例 2 与前一个类似，但现在收银员 2 最多可以处理 2 个商品。因此，最优做法是将所有 bit 都分配给一个机器人，并让该机器人使用收银员 2。这样总共需要 $1$ 秒每个商品加上 $2$ 秒，共 $4$ 秒。

在样例 3 中，最优策略是让一个机器人带着 2 个 bit 去找收银员 2，另外两个机器人各带 1 个 bit 去找其他任意收银员。

数据范围

• $1 \leqslant \mathbf{T} \leqslant 100$。
• 对所有 $i$，$1 \leqslant \mathbf{M}_{\mathbf{i}} \leqslant 10^{9}$。
• 对所有 $i$，$1 \leqslant \mathbf{S}_{\mathbf{i}} \leqslant 10^{9}$。
• 对所有 $i$，$1 \leqslant \mathbf{P}_{\mathbf{i}} \leqslant 10^{9}$。
• $\mathbf{M}_{\mathbf{i}}$ 中最大的 $\mathbf{R}$ 个数之和 $\geqslant \mathbf{B}$。（即至少存在一组 $\mathbf{R}$ 个收银员可以处理所有 bit。）

测试点 1（11 分，公开）

• $1 \leqslant \mathbf{R} \leqslant \mathbf{C} \leqslant 5$。
• $1 \leqslant \mathbf{B} \leqslant 20$。

测试点 2（21 分，隐藏）

• $1 \leqslant \mathbf{R} \leqslant \mathbf{C} \leqslant 1000$。
• $1 \leqslant \mathbf{B} \leqslant 10^{9}$。

由 ChatGPT 4.1 翻译