题目描述

某座城市为鼓励市民乘坐公共交通，推出了地铁换乘公交的优惠方案：

1. 乘坐地铁后可获得一张优惠票，有效期为 45 分钟，期间可免费乘坐一次票价不高于该地铁票价的公交车。有效期指公交车出发时间与地铁出发时间之差不超过 45 分钟，即 $t_{bus} - t_{subway} \leq 45$。
2. 优惠票可累积，即可以连续乘坐多次地铁后再使用优惠票乘公交。
3. 乘坐公交车时，若手中有可用优惠票则必须使用；若有多张满足条件的优惠票，优先使用最早获得的那张。

现给出小明最近的乘车记录，请帮他计算总花费。

输入格式

第一行一个正整数 $n$，表示乘车记录的条数。

接下来 $n$ 行，每行三个整数，相邻两数之间以空格分隔。第 $i$ 行的第 1 个整数表示交通工具类型（$0$ 表示地铁，$1$ 表示公交车）；第 2 个整数表示票价 $price_i$；第 3 个整数表示开始乘车的时间 $t_i$（距 $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

提示

样例 1 说明

第 1 条记录：第 3 分钟花费 10 元乘地铁。

第 2 条记录：第 46 分钟乘公交，使用第 1 条记录获得的优惠票，免费。

第 3 条记录：第 50 分钟花费 12 元乘地铁。

第 4 条记录：第 96 分钟乘公交，距第 3 条记录的地铁已超过 45 分钟，优惠票失效，花费 3 元。

第 5 条记录：第 110 分钟花费 5 元乘地铁。

第 6 条记录：第 135 分钟乘公交，手中仅第 5 条记录的优惠票有效，但票价 6 元高于地铁票价 5 元，不能使用，花费 6 元。

总花费 36 元。

样例 2 说明

第 1 条记录：第 1 分钟花费 5 元乘地铁。

第 2 条记录：第 16 分钟花费 20 元乘地铁。

第 3 条记录：第 23 分钟花费 7 元乘地铁。

第 4 条记录：第 31 分钟乘公交，第 2 条记录的优惠票可用（票价 20 \geq 18），使用之。

第 5 条记录：第 38 分钟乘公交，第 1 条和第 3 条记录的优惠票均可使用，优先使用最早获得的第 1 条。

第 6 条记录：第 68 分钟乘公交，使用第 3 条记录的优惠票。

总花费 32 元。

数据规模与约定

对于 $30\%$ 的数据，$n \leq 1000$，$t_i \leq 10^6$。

另有 $15\%$ 的数据，$t_i \leq 10^7$，所有 $price_i$ 相等。

另有 $15\%$ 的数据，$t_i \leq 10^9$，所有 $price_i$ 相等。

对于 $100\%$ 的数据，$n \leq 10^5$，$t_i \leq 10^9$，$1 \leq price_i \leq 1000$。