捕捉 Snuke (1D)

题目描述

高桥君正在尝试捕捉许多 Snuke。

在数轴上有 5 个坑，坐标分别为 $0$、$1$、$2$、$3$、$4$，与 Snuke 的巢穴相连。

现在，$N$ 只 Snuke 将从坑中出现。已知第 $i$ 只 Snuke 会在时间 $T_i$ 从坐标 $X_i$ 的坑中出现，其大小为 $A_i$。

高桥君在时间 $0$ 位于坐标 $0$，可以在数轴上以最大速度 $1$ 移动。

当且仅当 Snuke 出现时他恰好位于该坑的坐标处，才能捕捉到这只 Snuke。

捕捉 Snuke 所需的时间可以忽略不计。

求高桥君通过最优移动能够捕捉到的 Snuke 大小之和的最大值。

输入格式

输入按以下格式从标准输入给出：

$N$
$T_1$ $X_1$ $A_1$
$T_2$ $X_2$ $A_2$
$\vdots$
$T_N$ $X_N$ $A_N$

输出格式

以整数形式输出答案。

样例

3
1 0 100
3 3 10
5 4 1

101

最优策略如下。

在坐标 $0$ 等待，在时间 $1$ 捕捉第一只 Snuke。

前往坐标 $4$，在时间 $5$ 捕捉第三只 Snuke。

无法同时捕捉第一只和第二只 Snuke，因此这是最优方案。

3
1 4 1
2 4 1
3 4 1

0

高桥君无法捕捉到任何 Snuke。

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

2978279323

数据范围

• $1 \le N \le 10^5$
• $0 \lt T_1 \lt T_2 \lt \ldots \lt T_N \le 10^5$
• $0 \le X_i \le 4$
• $1 \le A_i \le 10^9$
• 输入中的所有值均为整数