#119. 梦回红浪漫

梦回红浪漫

Background

土拨鼠小红终于长大了, 她选择了最喜欢的秘书工作

Description

她为了赚取更多的劳务费, 她把自己一天的时间做了规划, 今天有nn个客人约了小红, 每个客人都有服务的起止时间ai,bia_i, b_i, 以及给出的酬劳viv_i, 时间用整数01060 \sim 10^6表示, 确保起始时间<=终止时间, 现在红红想知道, 自己最多可以获得多少酬劳?

注意, 一个时段只能服务一名顾客, 如果两名顾客的起止时间相同, 可服务于这两名顾客.

Format

Input

第1行一个整数n, 表示有n个客人

接下来nn行, 每行三个整数ai,bi,via_i, b_i, v_i

Output

输出一个整数, 表示小红所能获得的最大酬劳

Samples

3
1 2 1
2 3 2
1 3 4
4

Limitation

1s, 1024KiB for each test case.

1aibin106 1 \le a_i \le b_i \le n \le 10^6

1vi106 1 \le v_i \le 10^6