회의실

$K$개의 회의실이 있다. $N$개의 회의가 이 회의실들을 이용하려고 한다. 각 회의는 $1$부터 $N$까지 번호가 붙어 있다. 회의 $i$는 시작 시각 $s\_i$, 끝나는 시각 $e\_i$, 위약금 $w\_i$로 표현된다. 

이 회의실들은 매우 특이한 규칙에 따라 운영된다. 회의 $i$와 회의 $j$는 다음 조건 중 적어도 하나를 만족하면 관련있는 회의라고 부른다. 

1. 두 구간 $\[s\_i , e\_i]$와 $\[s\_j , e\_j]$의 공통된 구간이 존재할 때 (시작과 끝 시각만 겹치는 경우에도) $i$와 $j$는 관련있는 회의이다. 
2. 두 구간 $\[s\_i , e\_i]$와 $\[s\_j , e\_j]$의 공통된 구간이 존재하지 않지만, 다른 회의 $c$가 $i$와 관련있고 $\[s\_c , e\_c]$와 $\[s\_j , e\_j]$의 공통된 구간이 존재할 때 (시작과 끝 시각만 겹치는 경우에도) $i$와 $j$는 관련있는 회의이다.

회의들이 취소될 수 있어서 위의 정의는 취소되지 않은 회의들만 가지고 판단한다. 즉, 원래 관련있는 회의 관계였던 두 회의가, 일부 회의의 취소로 인해 관련있는 회의 관계가 아니게 될 수 있다. 

취소되지 않은 회의는 회의실을 하나씩 할당받아야 한다. 관련있는 회의들은 모두가 반드시 서로 다른 회의실을 할당받아야 한다. 예를 들어 세 회의 $\[1,3]$, $\[3,5]$, $\[5,7]$는, $\[1, 3]$과 $\[5, 7]$ 사이에 공통된 구간이 없음에도 불구하고, 두 개가 아닌 세 개의 회의실을 할당받아야 함에 유의하시오. 회의실이 $K$개밖에 없기 때문에 일부 회의들을 취소해야 할 수 있다. 회의 $i$를 취소하면 위약금 $w\_i$를 내야 하므로, 가급적 취소할 회의를 잘 골라서 지급할 위약금의 합을 최소로 하고 싶다. 

다음 그림은 5개의 회의 $\[1, 4]$, $\[3, 6]$, $\[5, 8]$, $\[7, 10]$, $\[9, 12]$가 있고, 각 회의의 위약금이 차례로 1, 2, 5, 2, 1인 경우를 보이고 있다. 회의실이 2개 있다고 하자. 왼쪽의 예는 $\[5, 8]$을 취소해서 조건을 만족시키는 경우이며, 이 경우 위약금은 $5$이다. 오른쪽의 예는 $\[3, 6]$과 $\[9, 12]$를 취소해서 조건을 만족시키는 경우이며, 이 경우 위약금은 $3$이다. 모든 경우를 고려해보면 최소의 위약금 합은 $3$임을 알 수 있다. 

첫째 줄에 공백으로 구분된 두 정수 $N$, $K$가 주어진다.

다음 $N$개의 줄에는 공백으로 구분된 세 정수 $s\_i$, $e\_i$, $w\_i$가 주어진다.

주어진 회의실의 수와 회의 정보를 바탕으로, 조건을 만족하게 하기 위해서 취소해야 할 회의들 중 가장 위약금의 합이 적은 경우를 찾고 그때의 위약금의 합을 출력한다.

• $1 \le K \le N$
• $1 \le N \le 2\\,500$ 
• $1 \le s\_i \le e\_i \le 10^9$ $(1 \le i \le N)$
• $1 \le w\_i \le 10^9$ $(1 \le i \le N)$