劲歌金曲,美味菜肴

劲歌金曲
(If you smiled when you see the title, this problem is for you ^_)
给n首歌和一个时间t，最后一首歌必须是劲歌金曲(这首歌的时间是678s)，要求t时间内唱的歌的数目最多的前提下使唱的时间最大。

美味菜肴
小明是个大厨，早上起来他开始一天的工作。他所在的餐厅每天早上都会买好n件食材（每种食材的数量可以视为无限），小明从到达餐厅开始就连续工作T时间。每道菜肴的制作需要特定的一种食材以及一段时间，但是食材一旦放久就不新鲜了，菜的美味值会降低。第i道菜肴有三个属性ai，bi，ci，ai是该菜肴的美味值，bi是该菜肴所选食材不新鲜的速率，如果在第t时刻完成第i道菜则美味值为：ai-t*bi，完成这道菜需要ci的时间。小明希望在这T时间内能做出菜肴使得总美味值最大，所以小明求助于你。

第1行输入三个整数n，m，T，分别代表食材种类，菜肴种类和工作时间。
第2行输入n个整数bi，代表第i个食材不新鲜的速率。
第3-n+2行，每行输入三个整数j，ai，ci，分别代表第i道菜肴需要的食材编 ，菜肴的美味值，完成时间。
数据保证：0