2019 T2 公交换乘

主知识点：队列与滑动窗口。交叉标签：队列、滑动窗口、贪心、模拟。
暴力标注：不属于重点 DP 退路题。
OJ 使用标准输入与标准输出。原比赛文件名为 transfer.in / transfer.out；下方如保留原文件约定，以本句的 OJ 约定为准。
时限 1 秒；内存 256 MiB；测试点 20；总分 100。
数据来源：官网数据；与公开存档逐文件一致。

题目描述

按时间顺序给出若干次乘车记录，包括交通方式、票价和乘坐时刻。乘地铁需付费，取得一张相应票价的地铁票；此票在之后 45 分钟内（含第 45 分钟）可用于一次免费公交，公交票价不能高于该地铁票。

乘公交时，如有多张可用地铁票，使用最早取得的那张；一张票只能使用一次。无法使用优惠票则支付公交票价。求全部行程的实际总花费。

输入格式

输入文件的第一行包含一个正整数 $n$，代表乘车记录的数量。

接下来的 $n$ 行，每行包含 3 个整数，相邻两数之间以一个空格分隔。第 $i$ 行的第 1 个整数代表第 $i$ 条记录乘坐的交通工具，0 代表地铁，1 代表公交车；第 2 个整数代表第 $i$ 条记录乘车的票价 $price_i$； 第 $3$ 个整数代表第 $i$ 条记录开始乘车的时间 $t_i$（距 0 时刻的分钟数）。

我们保证出行记录是按照开始乘车的时间顺序给出的，且不会有两次乘车记录出现在同一分钟。

输出格式

输出文件有一行，包含一个正整数，代表小轩出行的总花费。

样例

样例 1

输入：

6
0 10 3
1 5 46
0 12 50
1 3 96
0 5 110
1 6 135

输出：

36

样例 2

输入：

6
0 5 1
0 20 16
0 7 23
1 18 31
1 4 38
1 7 68

输出：

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$。

附加样例

本题的公开样例整理在对应的“样例”ZIP 中。样例不计入评测测试点；题面中的样例也已保留。

来源与整理说明

题目原作者/发布者：中国计算机学会 CCF / NOI。题意经过改写，保留公式、输入输出、样例及约束；知识点和暴力标注为本次整理补充。

• 题面及约束校对来源：洛谷 CCF_NOI 题目 P5661
• 赛事：CSP-J 第二轮入门级 2019。
• 详细数据来源、版本和哈希见总包 来源与校验/manifest.json。