如今，机器人可以驾驶汽车，但它们能举办一场精彩的派对吗？Code Jam 团队对这一课题的研究尚处于早期阶段。我们刚刚部署了 $R$ 个机器人购物者到当地超市购买派对用品，用于我们在多伦多的全球总决赛，但它们对加拿大派对的初步模型非常简单：它们只购买了 $B$ 个“比特”（bit，当地的一种小型甜甜圈状零食）。我们稍后会改进它们的 AI，但现在，我们想帮助它们尽快买齐所有这些比特。

超市有 $C$ 个收银员可以扫描顾客的购买商品。第 $i$ 个收银员： 每位顾客最多接受 $M_i$ 个商品。 扫描每个商品需要 $S_i$ 秒。 * 处理付款和打包比特还需要 $P_i$ 秒。

也就是说，携带 $N$ 个比特到第 $i$ 个收银员处的顾客（其中 $N$ 必须小于或等于 $M_i$）与该收银员交互的总时间为 $S_i \times N + P_i$ 秒。

在机器人与任何收银员交互之前，你可以随意将比特分配给机器人。（比特必须保持完整；你不能将它们拆分成碎片！）任何没有获得比特的机器人将无法与收银员交互，并会失望地离开。

然后，对于每个至少拥有一个比特的机器人，你将选择一个不同的收银员。（两个机器人不能使用同一个收银员，且一个机器人不能使用超过一个收银员。）所有机器人在时间 0 开始与它们的收银员交互。注意，一旦机器人完成与收银员的交互，它就不能再被给予更多比特，也不能与其他收银员交互。

如果你帮助机器人做出最优选择，所有机器人完成与收银员交互的最早时间是多少？

输入格式

输入的第一行给出测试用例的数量 $T$。接着是 $T$ 个测试用例。每个测试用例的第一行包含三个整数 $R$、$B$ 和 $C$：分别是机器人购物者、比特和收银员的数量。

然后有 $C$ 行。第 $i$ 行代表第 $i$ 个收银员，包含三个整数 $M_i$、$S_i$ 和 $P_i$：分别是该收银员的最大比特数、每个比特的扫描时间（秒）以及付款/打包时间（秒），如上所述。

输出格式

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

数据范围

$1 \le T \le 100$。 $1 \le M_i \le 10^9$，对于所有 $i$。 $1 \le S_i \le 10^9$，对于所有 $i$。 $1 \le P_i \le 10^9$，对于所有 $i$。 $R$ 个最大的 $M_i$ 之和 $\ge B$。（至少存在一个收银员子集能够处理所有比特。）

子任务

测试集 1（可见） $1 \le R \le C \le 5$。 $1 \le B \le 20$。

测试集 2（隐藏） $1 \le R \le C \le 1000$。 $1 \le B \le 10^9$。

样例

样例输入 1

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

样例输出 1

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

说明

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

样例 2 与前一个案例类似，不同之处在于现在收银员 2 最多可以处理 2 个商品。因此，最好将所有比特给一个机器人，并让该机器人使用收银员 2。这需要每个商品 1 秒加上 2 秒 = 4 秒。

在样例 3 中，最优策略是派遣一个携带 2 个比特的机器人到收银员 2，并派遣两个各携带 1 个比特的机器人到其他任意收银员处。