구간 삭제

시간 제한1초메모리 제한1024 MB

요약

수직선 위 구간을 일부 삭제해 서로 겹쳐 이어진 묶음의 크기가 K를 넘지 않게 하는 최소 삭제 비용을 구합니다.

난이도: 보통10점 중 6점
유형: 구간, 동적 계획법, 정렬
정답자: 아직 제출이 없습니다

문제

수직선 위에 $N$ 개의 구간이 있으며, 각각 $1$ 부터 $N$ 까지 번호가 매겨져 있다. $i$ 번 구간의 양 끝점은 $S_i$ 와 $E_i$ 이다. 구간마다 정점이 하나씩 대응하는 그래프 $G$ 를 생각한다. 두 구간이 공통된 점을 가지면(끝점만 공유하는 경우도 포함) 대응하는 두 정점 사이에 간선이 있다.

이 그래프의 어느 연결 요소도 정점이 $K$ 개를 넘지 않아야 한다. 이를 위해 주어진 구간 중 일부를 삭제할 수 있다. $i$ 번 구간을 삭제하는 데는 정해진 비용 $W_i$ 가 든다. 삭제 비용의 합이 최소가 되는 방법을 구하라.

입력

첫 줄에 정수 $N$ 과 $K$ 가 주어진다( $1 \le K \le N \le 2\,500$ ). 이어지는 $N$ 개의 줄에는 각각 구간 하나의 정보인 정수 $S_i$ , $E_i$ , $W_i$ 가 주어진다( $1 \le S_i \le E_i \le 10^9$ , $1 \le W_i \le 10^9$ ).

출력

삭제 비용의 합의 최솟값을 한 줄에 출력한다.

예제3

예제 1
입력
```
5 2
1 4 1
3 6 2
5 8 5
7 10 2
9 12 1
```
예상 출력
```
3
```

예제 2

입력

예상 출력

예제 3

입력

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

예상 출력

5000000000