문제
어느새 또 한 해가 끝나간다. 크리스마스 캐럴과 은은하게 반짝이는 꼬마 전구들이 거리를 수놓고 있다. 사람들의 얼굴에는 희망과 후련함이 비친다. 하지만 어떤 사람들의 얼굴에는 아쉬움도, 불안감도 함께 옅은 그림자를 그리고 있다.
2021년을 떠나 보내는 홍윤이는 행복하다. 홍윤이는 오늘 사람들에게 행복을 선물하기로 했다.
오늘 밤 무한히 긴 수직선의 도로를 따라 N명의 사람들이 저마다의 시간을 보낼 것이다.
i번째 사람은 오늘 밤 동안 수직선의 l_i 위치에서 양의 방향으로 걷기 시작해 r_i 위치에서 도로를 떠날 예정이다.
홍윤이는 K병의 향수를 가지고 있다. 홍윤이의 향수에는 마법같은 힘이 있어 맡는 사람을 행복하게 해준다. 그 정도는 사람마다 다를 수 있는데, 구체적으로 오늘 밤 도로를 지나갈 N명의 사람 중 i번째 사람은 향을 맡으면 w_i만큼의 행복도를 얻는다.
홍윤이는 도로에 향수병을 적절히 배치해 사람들이 얻는 행복도의 합을 최대화 하고 싶다.
하지만 심한 바람 때문에 어떤 사람이 향을 맡기 위해서는 정확히 향수병이 놓인 위치를 지나가야 한다. 향수병을 경로의 끝점에서 만나도 향을 맡을 수 있으며, 한 사람이 향을 여러 번 맡더라도 딱 한 번만 행복도를 얻을 수 있다.
홍윤이를 도와 사람들에게 행복을 선물하며 한 해를 마무리해보자.
입력
첫 줄에 N, K가 공백을 사이에 두고 주어진다. (1 <= K <= N <= 200,000)
이후 N줄에 걸쳐 i번째 줄에는 l_i, r_i, w_i가 차례대로 공백을 사이에 두고 주어진다.
(-10^9 <= l_i <= r_i <= 10^9, 1 <= w_i <= 10,000)
출력
K개의 향수를 최적으로 배치했을 때 사람들이 얻을 수 있는 행복도의 합의 최대값을 한 줄에 출력하라.
예제
7 2
1 2 10
2 5 8
3 7 3
4 6 1
7 8 5
8 9 9
9 10 2
32
로그인해야 코드를 작성할 수 있어요.