14385 - 军列转运调度
时间限制 : 1 秒
内存限制 : 128 MB
抗战时期,某后勤转运站采用 铁路 + 公路 接力运输方案来节约运力:
1、每发出一节铁路军列后,可获得一张转运优惠凭证,有效期 45 分钟。
2、在有效期内可凭此凭证免费调用一辆公路卡车,公路卡车的运输费用不超过该节铁路军列的运输费用。
3、有效期判定:t卡车 − t铁路 ≤ 45。
铁路军列发出的优惠凭证可以累积,即可连续发出多节铁路军列后再连续调用公路卡车。调用公路卡车时,若有可用优惠凭证则必须使用;若有多张凭证同时满足条件,优先消耗最早获得的那张。
现有一份按时间顺序排列的运输记录,请计算总运输费用。
输入
第一行包含一个正整数 n,代表运输记录的数量。
接下来的 n 行,每行包含 3 个整数,相邻两数之间以一个空格分隔。第 i 行的第 1 个整数代表第 i 条记录使用的运输工具,0 代表铁路军列,1 代表公路卡车;第 2 个整数代表第 i 条记录的运输费用 pricei;第三个整数代表第 i 条记录开始运输的时间 ti,距 0 时刻的分钟数。
我们保证运输记录是按照开始运输的时间顺序给出的,且不会有两次运输记录出现在同一分钟。
输出
只有一行,包含一个正整数,代表本次转运任务的总运输费用。
样例
输入
6 0 10 3 1 5 46 0 12 50 1 3 96 0 5 110 1 6 135
输出
36
输入
6 0 5 1 0 20 16 0 7 23 1 18 31 1 4 38 1 7 68
输出
32