← 返回题目列表

AtCoder · abc266_d

G. 潜核恐慌 (1D)

中文机器翻译题面 查看原题

分数: 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