Deleting Segments

Time limit1sMemory limit1024 MB

Summary

Delete the cheapest set of segments on a number line so that no group of mutually connected overlapping segments has more than K members.

Level: Medium6 of 10
Topics: Intervals, Dynamic programming, Sorting
Solved: No attempts yet

Statement

A number line has $N$ segments numbered $1 \ldots N$ . Segment $i$ has endpoints $S_i$ and $E_i$ . Consider a graph $G$ with one vertex per segment, where two vertices are connected by an edge if their segments share at least one point (even if they only share an endpoint).

You must make sure that no connected component of this graph has more than $K$ vertices. To do this, you may delete some of the given segments. Deleting segment $i$ costs a fixed price $W_i$ . Find a way to delete segments with the minimum total price.

Input

The first line contains integers $N$ and $K$ ( $1 \le K \le N \le 2\,500$ ). Each of the next $N$ lines describes one segment with three integers $S_i$ , $E_i$ , and $W_i$ ( $1 \le S_i \le E_i \le 10^9$ , $1 \le W_i \le 10^9$ ).

Output

Print the minimum total price of the deletions on a single line.

Examples3

Example 1
Input
```
5 2
1 4 1
3 6 2
5 8 5
7 10 2
9 12 1
```
Expected output
```
3
```

Example 2

Input

Expected output

Example 3

Input

6 1
1 2 1000000000
1 2 1000000000
1 2 1000000000
1 2 1000000000
1 2 1000000000
1 2 1000000000

Expected output

5000000000