충전기 한 대의 예약표

문제

어느 전기차 충전소에는 급속 충전기가 한 대뿐이다. 오늘 하루 동안 N건의 예약 신청이 들어와 있다. i번째 신청은 충전을 시작하는 시각 s_i, 충전을 마치는 시각 e_i(s_i < e_i), 그리고 이 예약을 받았을 때 얻는 수익 p_i로 이루어진다. 충전기는 한 번에 한 대의 차량만 쓸 수 있다. 또한 충전이 끝난 뒤에는 케이블 점검과 냉각을 위해 G 단위 시간 이상의 휴지 시간이 필요하다. 즉 예약 a를 받은 다음에 예약 b를 이어서 받으려면 e_a + G ≤ s_b 여야 한다. 등호가 성립하는 경우, 곧 휴지 시간이 정확히 G인 경우도 허용된다. G가 0이면 한 예약이 끝나는 순간 다음 예약이 시작해도 된다. 신청은 받을 수도 있고 거절할 수도 있으며, 받은 예약들을 시간순으로 늘어놓았을 때 이웃한 두 예약이 모두 위 조건을 만족해야 한다. 시각 구간이 완전히 같은 신청이 여러 개 있을 수 있고, 각각은 서로 다른 신청으로 취급한다. 받은 예약들의 수익 합이 최대가 되도록 고를 때, 그 최대 수익과, 최대 수익을 달성하는 선택 중 받는 예약 수의 최솟값을 구하는 프로그램을 작성하라.

입력

첫 줄에 정수 N과 G가 공백으로 구분되어 주어진다. 이어서 N개의 줄에 걸쳐 s_i e_i p_i가 공백으로 구분되어 주어진다. 1 ≤ N ≤ 200000, 0 ≤ G ≤ 10^9, 0 ≤ s_i < e_i ≤ 10^9, 1 ≤ p_i ≤ 10^9이며 모든 값은 정수다.

출력

최대 수익과 그때의 최소 예약 수를 공백으로 구분하여 한 줄에 출력한다.

4 1
0 3 5
3 5 4
4 8 6
6 9 5

11 2

3 0
0 2 3
2 4 3
1 3 5

6 2

1 5
0 10 7

7 1

출처: Devin.KR 자체 제작