Problem 1117. -- 张老师很有钱

1117: 张老师很有钱

Time Limit: 1 Sec  Memory Limit: 512 MB
Submit: 21  Solved: 9
[Submit][Status][Web Board]

Description

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

Input

题目包含多组数据。
第一行一个整数T,表示有T组测试数据。(T ≤ 10)
对于每组数据分为k+1行:
第1行,三个正整数n,m,k(n 10, m1000, k100),n表示有n个房间,m表示有m万元,k表示剩余的家具数量。
每行有三个正整数ci, ri, vi (cim, rin, vi1000),表示第i件家具的价格为ci万元,张老师觉得可以放入第ri号房间,家具的舒适度为vi

Output

对于每组数据,第一行输出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))

Sample Input

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

Sample Output

Case #1:
0
Case #2:
200

HINT

Source

[Submit][Status]