#503. 「新年欢乐赛 2019」homework

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Wahacer

题目描述

题目背景:Ghoster又咕咕咕了作业

又是一个寒假,Ghoster自然不会放过这个爆肝游戏的机会,但是山一样的寒假作业阻挡了Ghoster的爆肝计划,作为鸽子联盟首领的Ghoster自然是不会按时完成作业的,凭着多年的咕咕咕经验,他发现在寒假结束之后,老师不会检查全部的作业,只会查看作业的完成度,也就是说只要达到指定的完成度开学就不会被老师锤爆。

Ghoster现在有 n 项作业,每项作业有三个属性,耗时 t ,完成度 c 和肝度 g ,现在Ghoster决定从他肝游戏的时间里抽出 m 小时来完成作业,Ghoster不想在作业上爆肝,他想把剩下的肝用来肝全境封锁,请你帮Ghoster算出他在 m 小时内达到指定完成度 k 时花费的最小肝度是多少(可以超过完成度),如果Ghoster可以在 m 小时内达到指定完成度 k ,请输出最小的肝度,否则输出Ghoster's liver bomb!!!

输入格式

输入共 n+1

第一行有 3 个整数 n,m,k ,第二行到第 n+1 每行 3 个整数 t,c,g 分别表示每项作业的需要时间,完成度和肝度。

输出格式

如果Ghoster能在 m 小时内达到指定完成度,输出最小的肝度,否则输出Ghoster's liver bomb!!!

样例

样例输入

5 10 10
1 1 1
4 8 2
3 2 1
5 2 3
7 5 10

样例输出

3

样例解释:

选择第二项作业与第三项作业能在规定时间内保证完成度的情况下达到最小肝度。

数据范围与提示

对于20%的数据n<=10,m,k<=50

对于40%的数据n<=50,m,k<=500

对于100%的数据n<=150,m,k<=1500,t<=m,c<=k,g<=1000