14385 - 军列转运调度

通过次数

0

提交次数

0

时间限制 : 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