题目内容

部门项目排期需要安排若干开发任务。现有 $m$ 个工单，第 $i$ 个工单占用时间区间 $[a_i,b_i)$，完成收益为 $w_i$。同一时刻只能执行一个工单，被选中的工单时间不能重叠；每个工单最多选一次，可选任意多个。若一个工单在时刻 $t$ 结束、另一个恰好在时刻 $t$ 开始，则二者不冲突。请给出能得到的最大总收益。

输入描述

首先一行一个整型 $m$（$1 \le m \le 250000$），表示工单数量。

随后 $m$ 行，每行三个整型 $a,b,w$（$0 \le a < b \le 1\times 10^9$，$1 \le w \le 1\times 10^9$），表示一个工单的开始时间、结束时间与收益。工单不保证按时间排序。

输出描述

写出一个非负整型，即最大总收益。答案可能超过 $32$ 位整数范围。

样例1

输入

3
0 2 10
2 4 20
1 3 100

输出

100

说明

选 $[1,3)$ 收益 $100$。若选相接的 $[0,2)$ 与 $[2,4)$，总收益只有 $30$。

样例2

输入

4
5 9 8
0 4 3
4 5 1
8 10 2

输出

12

说明

选 $[0,4)$、$[4,5)$、$[5,9)$，收益 $3+1+8=12$。三者在时刻 $4$、$5$ 相接，不冲突。