题目描述

高桥君在数轴上挖了 $5$ 个坑，坐标为 $0,1,2,3,4$。一开始他在 $0$ 位置，每秒最多移动 $1$ 单位。

现有 $n$ 条 Snuke，第 $i$ 条大小为 $A_i$，在第 $T_i$ 时刻出现在坐标为 $X_i$ 的坑。请注意出现仅发生在瞬间，下一时刻消失。

高桥君能抓到第 $i$ 条 Snuke 当且仅当某时刻他在第 $T_i$ 时刻出现在 $X_i$。请计算他抓到的 Snuke 总大小最大值。

输入格式

第一行输入 $N$

接下来 $N$ 行每行输入三个整数分别为 $T_i$ $X_i$ $A_i$

输出格式

输出一个整数代表答案

3
1 0 100
3 3 10
5 4 1

101

3
1 4 1
2 4 1
3 4 1

0

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\ \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$ 处捕捉第一个斯努克。
• 前往坐标 $4$ ，在时间 $5$ 捕捉第三只 Snuke。

不可能同时捕捉到第一只和第二只 Snuke，所以他只能这样做。