分数: 400 点
问题陈述
高桥正试图抓住许多 Snuke。
坐标处有五个坑 0, 1, 2, 3,和 4 在数轴上,连接到 Snuke 的巢穴。
现在, N 蛇将会从坑中出现。据了解, i-th Snuke将从坐标处的坑中出现 X_i 时间 T_i,其大小为 A_i.
高桥在坐标 0 时间 0 并且可以在线上以最高速度移动 1.
当且仅当他在蛇出现时正好位于该坑的坐标处时,他才能抓住从坑中出现的蛇。
捕捉 Snuke 所需的时间可以忽略不计。
求高桥通过最佳移动可以捕获的 Snuke 大小的最大总和。
约束
- 1 \leq N \leq 10^5
- 0 < T_1 < T_2 < \ldots < T_N \leq 10^5
- 0 \leq X_i \leq 4
- 1 \leq A_i \leq 10^9
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N T_1 X_1 A_1 T_2 X_2 A_2 \vdots T_N X_N A_N
输出
将答案打印为整数。
示例输入 1
3 1 0 100 3 3 10 5 4 1
示例输出 1
101
最优策略如下。
- 在坐标处等待 0 及时抓住第一个 Snuke 1.
- 转到坐标 4 及时抓住第三个 Snuke 5.
不可能同时抓住第一个和第二个 Snuke,所以这是他能做的最好的了。
示例输入 2
3 1 4 1 2 4 1 3 4 1
示例输出 2
0
高桥无法抓住任何 Snuke。
示例输入 3
10 1 4 602436426 2 1 623690081 3 3 262703497 4 4 628894325 5 3 450968417 6 1 161735902 7 1 707723857 8 2 802329211 9 0 317063340 10 2 125660016
示例输出 3
2978279323