407308: GYM102759 F Interval Graph

Memory Limit:1024 MB Time Limit:3 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

F. Interval Graphtime limit per test3 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard output

You are given $$$N$$$ closed intervals. The $$$i$$$-th interval has the range $$$[s_i, e_i]$$$, and has a positive integer weight $$$w_i$$$. Consider the undirected graph of $$$N$$$ vertices, where each vertex corresponds to an interval, and there exists an edge between two vertices if and only if the corresponding pair of intervals has a nonempty intersection. For a given list of intervals, we call this graph the interval graph.

Jaehyun is addicted to problems about trees and queries, so he wants the graph to be acyclic. To accomplish this, he can delete zero or more intervals. Jaehyun is lazy, so over all possible ways to delete intervals, he will select the way which minimizes the weight of the intervals he has to delete. Print the weight of the remaining intervals after he has made the interval graph acyclic.

Input

The first line contains the single integer $$$N$$$ ($$$1 \le N \le 250\,000$$$).

The next $$$N$$$ lines contain three space-separated integers $$$s_i, e_i, w_i$$$ ($$$1 \le s_i \le e_i \le 500\,000$$$, $$$1 \le w_i \le 10^{12}$$$).

Output

Print the weight of the remaining intervals after Jaehyun's deletions.

ExamplesInput
3
1 3 10
3 5 20
5 7 30
Output
60
Input
3
1 3 1
2 3 2
3 3 3
Output
5

加入题单

上一题 下一题 算法标签: