当前没有测试数据。

题目描述

小明经营着一家小公司，公司每天可以承接一个项目。现有 $n$ 个项目可供选择，第 $i$ 个项目需要从第 $L_i$ 天开始到第 $R_i$ 天结束（包含两端），完成该项目可以获得收益 $W_i$。

公司同一时间只能承接一个项目，即所选项目的执行时间段不能有重叠。请选择一些项目，使得总收益最大。

输入格式

第一行输入一个整数 $n$，表示项目数量。

接下来 $n$ 行，每行三个整数 $L_i, R_i, W_i$，表示第 $i$ 个项目的开始时间、结束时间和收益。

输出格式

输出一个整数，表示最大总收益。

样例 #1

输入

4
1 3 10
2 5 15
4 6 20
6 8 25

输出

35

样例 #2

输入

5
1 4 20
2 5 30
4 7 25
6 9 35
8 10 15

输出

55

样例说明

样例 1 解释

选择项目 1（收益 10）和项目 4（收益 25），总收益为 35。项目 1 结束于第 3 天，项目 4 开始于第 6 天，没有重叠。

数据范围

对于 $30\%$ 的数据，$1 \le n \le 20$。

对于 $100\%$ 的数据，$1 \le n \le 10^5$，$1 \le L_i \le R_i \le 10^9$，$1 \le W_i \le 10^6$。