题目描述

有钱的张老师又双叒叕新买了一栋别墅。既然是一栋别墅，所以一共有 $n$ 个房间。因为张老师很有钱，所以这 $n$ 个房间他都打算留给自己住。因为张老师很有钱，所以他希望这 $n$ 个房间中最不舒适的房间也有尽可能高的舒适度，而一个房间的舒适度在张老师看来是直接取决于房间中家具的舒适度总和。张老师虽然很有钱，但他还是希望低调一点，所以他决定拿出 $m$ 万元来为添置家具。所以现在张老师带着这 $m$ 万元来到了他最喜欢的家具店。由于张老师最近买了太多的房子，所以他最喜欢的家具店存货已经不足了，只剩下了 $k$ 个家具。所以张老师写下了对于每个家具他认为适合放入哪个房间当中（房间的编号为 $1$ 到 $n$），然后就把这份清单交给了身为秘书的你，让你帮他把家具添置到每个房间当中，使最后 $n$ 个房间中舒适度最低的房间舒适度最高。（因为有钱任性，张老师并不介意一个房间当中放上多个相同类型的家具。）

输入格式

题目包含多组数据。

第一行一个整数 $T$，表示有 $T$ 组测试数据。（$T \leq 10$）

对于每组数据分为 $k+1$ 行：

第 $1$ 行，三个正整数 $n$, $m$, $k$（$n \leq 10$，$m \leq 1000$，$k \leq 100$），$n$ 表示有 $n$ 个房间，$m$ 表示有 $m$ 万元，$k$ 表示剩余的家具数量。

接下来 $k$ 行，每行有三个正整数 $c_i$, $r_i$, $v_i$（$c_i \leq m$，$r_i \leq n$，$v_i \leq 1000$），表示第 $i$ 件家具的价格为 $c_i$ 万元，张老师觉得可以放入第 $r_i$ 号房间，家具的舒适度为 $v_i$。

输出格式

对于每组数据，第一行输出 Case #x:（$x$ 编号从 $1$ 开始）。

第 $2$ 行，一个整数，表示最终能够使舒适度最低的房间达到的最高舒适度。（例如有三个房间，舒适度的选择有 $(3,7,8)$ 和 $(5,6,6)$。则我们应该选取 $(5,6,6)$ 这种方案，因为 $(3,7,8)$ 的最低舒适度为 $3$，$(5,6,6)$ 的舒适度为 $5$。所以为了让最低舒适度最高，所以我们应该选择方案 $(5,6,6)$。）

样例输入

2
2 1000 3
500 1 300
400 1 500
900 1 1000
2 1000 3
500 1 400
300 2 200
600 2 500

样例输出

Case #1:
0
Case #2:
200