#LQ1424. 小蓝的旅行计划

小蓝的旅行计划

问题描述

小蓝正计划进行一次漫长的旅行。小蓝计划开车完成这次旅行。显然他在途中需要加油,否则可能无法完成这次旅行。

小蓝要依次经过 nn 个地点,其中从第 i1i-1 个地点到达第 ii 个地点需要消耗 DisiDis_i 升油。小蓝经过的每个地点都有一个加油站,但每个加油站的规定也不同。在第 ii 个加油站加 11 升油需要 CostiCost_i​ 的费用,且在这个加油站最多只能加 LiL_i 升油。

小蓝的车的油箱也有容量限制,他的车上最多只能装载 mm 升油。一开始小蓝的油箱是满的,请问小蓝需要准备多少钱才能顺利完成他的旅行计划。如果小蓝按给定条件无论准备多少钱都不能完成他的旅行计划,请输出 -1

输入格式

输入的第一行包含两个整数 nnmm,用一个空格分隔。 接下来 nn 行每行包含 33 个整数 DisiDis_iCostiCost_i​,LiL_i,相邻整数之间使用一个空格分隔。

输出格式

输出一行包含一个整数表示答案。

样例

4 5
2 9 2
4 5 6
3 2 2
4 1 3
38

评测用例规模与约定

对于 30%30\% 的评测用例,n,Disi,Costi,Limi,m300n,Dis_i,Cost_i,Lim_i,m≤300

对于 60%60\% 的评测用例,n,Disi,Costi,Limi,m5000n,Dis_i,Cost_i,Lim_i,m≤5000

对于所有评测用例,1n2×1051≤n≤2×10^51Disi,Limi,m1091≤Dis_i,Lim_i,m≤10^91Costi400001≤Cost_i≤40000