Problem D: 持续攻击

上一题 正确率: $64.96\%$ 下一题
"
Time Limit $1$ 秒/Second(s) Memory Limit $128$ 兆字节/Megabyte(s)
提交总数 $117$ 正确数量 $76$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 贪心

Description

血魔遇到了N个敌人。初始血魔生命值为M，每秒钟血魔的生命值会减少1。如果血魔的生命值变为0，血魔会立刻消失，但在此之前他可以击杀敌人来恢复生命值。对于第i个敌人需要攻击Ti次才能杀死，血魔每秒钟可以攻击一次，每秒钟血魔可以攻击任意一个敌人，并且每次攻击可以同时击中任意多个敌人。敌人一共有K种类型，对于每种类型的敌人，血魔最多只能杀死一个。血魔在进行过所有攻击后，他可以立刻恢复他所杀死敌人的最小生命值，在恢复过后不能再继续进行攻击（如果血魔生命值变为0的瞬间恢复生命值，血魔不会死亡）。现在血魔想知道，他是否能杀死K个敌人，如果能的话，那么杀死K个敌人后，生命值最高能为多少？

Input

第一行3个整数N，M，K，分别表示敌人数量，血魔初始的生命值，敌人类型数。

接下来N行，每行三个整数Hi，Ti，Ci，分别表示第i个敌人的生命值，需要攻击的次数和类型。

1 <= Ci <= K <= N <= 105

1 <= Hi，Ti，M <= 109

保证每种类型的敌人至少有一个。

Output

如果不能杀死K个敌人输出-1，否则输出生命值最大值。

Sample Input复制

2 5 2
1 2 2
4 5 1

Sample Output复制

1