错拍之间（rhythm）

• 输入：rhythm.in
• 输出：rhythm.out
• 时间限制：2 s
• 内存限制：256 MB

题目描述

音符沿着轨道接连落下，判定线上的光芒随着按键不断闪烁。面对越来越密集的谱面，小 R 发现，有时稍稍推迟一个音符，就能接住另一个音符；有时也需要做出取舍，才能获得更高的总分。

小 R 正在游玩一款音游的单键挑战模式。游戏中的时刻用正整数编号，谱面中共有 $n$ 个音符。

第 $i$ 个音符有三个参数 $s_i,t_i,v_i$：

• 可以在任意满足 $s_i \le x \le t_i$ 的整数时刻 $x$，通过一次按键命中这个音符。
• 每个音符最多被命中一次，命中后获得 $v_i$ 分。
• 无论在判定窗口内的哪个时刻命中，获得的分数都相同。

**每个整数时刻最多进行一次按键，且一次按键只能命中一个音符。**相邻的两个整数时刻可以连续按键。

小 R 可以自由选择要命中的音符及其命中时刻，也可以放弃部分音符。未命中的音符不会扣分，游戏中也没有额外的连击奖励。

请你求出，小 R 最多可以获得多少总分。

输入格式

从文件 rhythm.in 中读入数据。

第一行包含一个正整数 $n$，表示音符数量。

接下来 $n$ 行，每行包含三个正整数 $s_i,t_i,v_i$，描述第 $i$ 个音符。

输出格式

输出到文件 rhythm.out 中。

输出一行一个整数，表示能够获得的最大总分。

5
1 2 10
1 1 9
2 3 8
3 3 7
2 2 6

27

样例1解释

一种最优安排是在时刻 $1,2,3$ 分别命中第 $2,1,3$ 个音符，总分为 $9+10+8=27$。

所有音符的判定窗口都在时刻 $1$ 至 $3$ 之间，因此最多命中三个音符。上述方案命中了得分最高的三个音符，所以是最优方案。

4
1 1 1000000000
1 1 999999999
1000000000 1000000000 1000000000
2 999999999 1000000000

3000000000

样例2解释

在时刻 $1,2,10^9$ 分别命中第 $1,4,3$ 个音符，总分为 $3 \times 10^9$。第 $1$、$2$ 个音符都只能在时刻 $1$ 命中，无法同时获得它们的分数。

数据范围

对于所有数据，$1 \le n \le 5000$，$1 \le s_i \le t_i \le 10^9$，$1 \le v_i \le 10^9$。每个测试点 $5$ 分。

特殊性质 A：对于所有音符，均有 $s_i=1$。

特殊性质 B：对于所有音符，均有 $v_i=1$。