Score : $400$ points

问题描述

高桥试图捕捉许多 Snuke。

在数轴上的坐标 $0$, $1$, $2$, $3$ 和 $4$ 处有五个坑，它们与 Snuke 的巢穴相连。

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

高桥在时间 $0$ 时位于坐标 $0$ 处，且可以在数轴上以不超过速度 $1$ 移动。
只有当他在 Snuke 出现时恰好位于该 Snuke 所在的坑的坐标处才能成功捕捉到它。
捕捉一只 Snuke 所需的时间可以忽略不计。

请计算通过最优移动策略，高桥最多能捕捉到的 Snuke 的大小之和。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

Takahashi is trying to catch many Snuke.

There are five pits at coordinates $0$, $1$, $2$, $3$, and $4$ on a number line, connected to Snuke's nest.

Now, $N$ Snuke will appear from the pits. It is known that the $i$-th Snuke will appear from the pit at coordinate $X_i$ at time $T_i$, and its size is $A_i$.

Takahashi is at coordinate $0$ at time $0$ and can move on the line at a speed of at most $1$.
He can catch a Snuke appearing from a pit if and only if he is at the coordinate of that pit exactly when it appears.
The time it takes to catch a Snuke is negligible.

Find the maximum sum of the sizes of Snuke that Takahashi can catch by moving optimally.

Constraints

• $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$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$

$T_1$ $X_1$ $A_1$

$T_2$ $X_2$ $A_2$

$\vdots$

$T_N$ $X_N$ $A_N$

Output

Print the answer as an integer.

Sample Input 1

3
1 0 100
3 3 10
5 4 1

Sample Output 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.

Sample Input 2

3
1 4 1
2 4 1
3 4 1

Sample Output 2

0

Takahashi cannot catch any Snuke.

Sample Input 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

Sample Output 3

2978279323

update @ 2024/3/10 11:14:52