← 返回题目列表

Codeforces · 777/E

E. 河内工厂

中文机器翻译题面 查看原题

你当然听说过河内塔这个著名的任务,但是你知道有一个专门的工厂为这个精彩的游戏生产戒指吗?曾几何时,古埃及的统治者命令河内工厂的工人们建造尽可能高的塔。他们还没有准备好服务如此奇怪的订单,因此他们必须使用已经生产的戒指来建造这座新塔。

工厂库存有 n 个戒指。第 i 个环具有内半径 ai、外半径 bi 和高度 hi。目标是选择环的一些子集并排列它们以满足以下条件:

- 外半径形成非递增序列,即只有当 bj ≤ bi 时才可以将第 j 个环放在第 i 个环上。
- 戒指不应掉入另一枚中。这意味着只有当 bj > ai 时才可以将环 j 放在环 i 上。
- 使用的所有环的总高度应尽可能大。

输入

输入的第一行包含一个整数 n (1 ≤ n ≤ 100 000) — 工厂库存中的戒指数量。

接下来 n 行的第 i 行包含三个整数 ai、bi 和 hi (1 ≤ ai, bi, hi ≤ 109, bi > ai)——分别是第 i 个环的内半径、外半径和高度。

输出

打印一个整数——可以获得的塔的最大高度。

示例

输入 #1

3
1 5 1
2 6 2
3 7 3

输出 #1

6

输入 #2

4
1 2 1
1 3 3
4 6 2
5 7 1

输出 #2

4

注意

在第一个示例中,最佳解决方案是取出所有环并按 3、2、1 的顺序将它们放在一起。

在第二个示例中,可以将环 3 放在环 4 上,得到高度 3 的塔,或者将环 1 放在环 2 上,得到高度 4 的塔。