AT_abc266_d [ABC266D] Snuke Panic (1D)

题目描述

高桥君正在尝试抓住“すぬけ君”们。

在数轴上的 $0, 1, 2, 3, 4$ 这 $5$ 个位置各有一个洞，通向“すぬけ君”们的巢穴。

接下来有 $N$ 只“すぬけ君”会从这些洞里出来。第 $i$ 只“すぬけ君”会在时刻 $T_i$ 从坐标 $X_i$ 的洞里出来，其大小为 $A_i$。

高桥君在时刻 $0$ 位于坐标 $0$，他可以在数轴上以每单位时间不超过 $1$ 的速度移动。 只有当高桥君在“すぬけ君”出现的同一时刻、同一坐标时，才能抓住这只“すぬけ君”，且仅限于这种情况。抓住“すぬけ君”所需时间可以忽略不计。

请计算高桥君合理行动时，最多能抓住的“すぬけ君”大小之和。

输入格式

输入以以下格式从标准输入给出。

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

输出格式

请输出答案的整数值。

输入输出样例 #1

输入 #1

3
1 0 100
3 3 10
5 4 1

输出 #1

101

输入输出样例 #2

输入 #2

3
1 4 1
2 4 1
3 4 1

输出 #2

0

输入输出样例 #3

输入 #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

说明/提示

限制条件

• $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$
• 输入中的所有数值均为整数。

样例解释 1

最优的行动方式如下：

• 在坐标 $0$ 等待，在时刻 $1$ 抓住第 $1$ 只“すぬけ君”。
• 移动到坐标 $4$，在时刻 $5$ 抓住第 $3$ 只“すぬけ君”。 无法同时抓住第 $1$ 只和第 $2$ 只“すぬけ君”，因此这就是最大值。

样例解释 2

高桥君无法抓住任何一只“すぬけ君”。

由 ChatGPT 4.1 翻译