팝콘

팝콘이 맛있는 간식이라는 건 누구나 안다. 올해 선발 캠프(와 뒤풀이)를 준비하는 동안 $N$가지 전자레인지용 팝콘을 주문했다. 종류마다 다음 세 값을 알고 있다.

• $A_i$: 종류 $i$ 팝콘이 터지는 시간(초)
• $B_i$: 종류 $i$ 팝콘이 타는 시간(초)
• $C_i$: 종류 $i$ 팝콘의 양

또한 용량이 매우 큰(사실상 무한한) 일회용 팝콘 봉투 $M$개와 전자레인지가 있다. 탄 팝콘과 터지지 않은 팝콘을 좋아하는 사람은 없으니, 팝콘을 $M$개 봉투에 나눠 담고 각 봉투의 가열 시간 $prep_j$를 정해 전자레인지에 넣는다. 결국 먹을 수 있는 팝콘이 최대한 많아야 한다.

형식적으로는, 봉투 $j$에 담긴 종류 $i$ 팝콘이 $prep_j$초 동안 가열되었을 때 $A_i \le prep_j < B_i$인 경우에만 먹을 수 있다.

$N$가지 팝콘과 봉투 수가 주어지면, 먹을 수 있는 팝콘이 가장 많아지도록 나누는 방법과 각 봉투의 가열 시간을 정하라. 먹을 수 있는 팝콘의 양을 출력하라. 아주 간단하다.

첫 줄에 정수 $N$과 $M$이 주어진다.

이어서 $N$개의 줄에 각각 팝콘 종류에 해당하는 정수 $A_i$, $B_i$, $C_i$가 주어진다.

먹을 수 있는 팝콘의 최대 양을 나타내는 정수 하나를 출력한다.

• $1 \le M \le N \le 200\,000$
• $1 \le A_i \le B_i \le 200\,000$
• 팝콘의 총량은 $10^9$을 넘지 않는다.
• 빈 봉투가 있어도 된다.
• $X=\max\{N,B_1,B_2,\dots,B_N\}$이라 하자.