409541: GYM103627 E Yet Another Interval Graph Problem

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

Description

E. Yet Another Interval Graph Problemtime limit per test1 secondmemory limit per test1024 mebibytesinputstandard inputoutputstandard output

You are given $$$N$$$ closed intervals. The $$$i$$$-th interval covers $$$[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 wants the graph to not have a connected component of size greater than $$$K$$$. 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 that minimizes the weight of the intervals he has to delete. Print the weight of the deleted intervals after he has made sure all connected components of the interval graph have size at most $$$K$$$.

Input

The first line contains two integers $$$N$$$ and $$$K$$$ ($$$1 \le K \le N \le 2500$$$).

Each of the next $$$N$$$ lines contains three integers $$$s_i, e_i, w_i$$$ ($$$1 \le s_i \le e_i \le 10^9$$$, $$$1 \le w_i \le 10^{9}$$$).

Output

Output the sum of the weights of the deleted intervals after Jaehyun's deletions.

ExampleInput
5 2
1 4 1
3 6 2
5 8 5
7 10 2
9 12 1
Output
3
Note

One possible solution is to remove the second and fifth intervals.

加入题单

上一题 下一题 算法标签: