D - 接住松尼鲑 (1D)

得分 : $400$ 分

问题描述

小高想接很多只松尼鲑。

有一个数轴上的5个坑洞，分别在坐标 $0$，$1$，$2$，$3$，$4$上，并与松尼鲑的巢窝相连。

现在会出现 $N$ 只松尼鲑。已知第 $i$ 只松尼鲑会在时刻 $T_i$ 从坐标 $X_i$ 处的坑洞出现，它的大小是 $A_i$。

小高在时刻 $0$ 位于坐标 $0$，他可以以不超过 $1$ 的速度在数轴上移动。
他可以在它出现的坑洞处接到松尼鲑。
接到一只松尼鲑的时间可以忽略不计。

请找出小高通过最优策略可以接到的松尼鲑大小的最大总和。

约束

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

输出

输出一个整数作为答案。

3
1 0 100
3 3 10
5 4 1

101

The optimal strategy is as follows.

• Wait at coordinate $0$ to catch the first Snuke at time $1$.
• Go to coordinate $4$ to catch the third Snuke at time $5$.

It is impossible to catch both the first and second Snuke, so this is the best he can.

3
1 4 1
2 4 1
3 4 1

0

Takahashi cannot catch any 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