链接: https://cses.fi/problemset/task/1140

板块: Dynamic Programming

时限: 1.00 s ｜ 内存: 512 MB

题目描述

你有 $n$ 个项目可以参加。对于每个项目，你知道它的起始日、结束日以及你能获得的报酬。一天之内你只能参加一个项目。

你能赚到的最大金额是多少？

输入

第一行输入包含一个整数 $n$：项目的数量。

之后有 $n$ 行。每行包含三个整数 $a_i$、$b_i$ 和 $p_i$：起始日、结束日和报酬。

输出

输出一个整数：你能赚到的最大金额。

数据范围

$1 \le n \le 2 \cdot 10^5$ $1 \le a_i \le b_i \le 10^9$ $1 \le p_i \le 10^9$

样例输入

4
2 4 4
3 6 6
6 8 2
5 7 3

样例输出

7