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