시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 1024 MB 60 19 16 32.653%

## 문제

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 wants the graph to not have a connected component of size greater $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 which minimizes the weight of the intervals he has to delete. Print the weight of the deleted intervals after he has made the size of the connected component of the interval graph at most $K$.

## 입력

The first line contains two space-separated integers $N, K$ ($1 \le K \le N \le 2500$).

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

## 출력

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

## 서브태스크

번호 배점 제한
1 10

$N \le 16$

2 17

$K = 1$

3 32

$w_i = 1$ for all $i$

4 26

$N \le 250$

5 65

## 예제 입력 1

5 2
1 4 1
3 6 2
5 8 5
7 10 2
9 12 1


## 예제 출력 1

3


## 채점 및 기타 정보

• 예제는 채점하지 않는다.
• 이 문제의 채점 우선 순위는 2이다.