换乘优惠

题目描述

某城市有轨道交通和公交车两种出行方式，所有乘车记录按时间严格递增给出。

每次乘坐轨道交通时：

1. 正常支付本次票价；
2. 获得一张面值等于本次票价的优惠券；
3. 优惠券从获得时刻开始 45 分钟内有效，恰好相差 45 分钟仍然有效；
4. 每张优惠券最多使用一次。

每次乘坐公交车时，按照优惠券获得时间从早到晚，寻找第一张同时满足下列条件的优惠券：

• 尚未使用；
• 没有过期；
• 面值不小于本次公交票价。

找到后本次公交免费，并将该优惠券标记为已使用；如果找不到，则正常支付公交票价。

请计算全部行程的实际总花费。

输入格式

第一行输入一个整数 n，表示乘车记录数量。

接下来 n 行，每行输入三个整数 type,price,time：

• type=0 表示轨道交通；
• type=1 表示公交车；
• price 表示票价；
• time 表示乘车时刻。

保证 time 严格递增。

输出格式

输出实际总花费。

样例

5
0 10 1
0 30 2
1 25 3
1 8 4
1 20 60

60

数据范围

1 <= n <= 100000，1 <= price <= 1000，1 <= time <= 10^9。