병원 예약의 준비 시간

문제

한 병원에서는 하나의 검사실에서 진행할 예약 신청을 받고 있다. 오늘 접수된 신청은 N개이며, 각 신청에는 검사 시작 시각, 검사 종료 시각, 그리고 해당 검사를 진행했을 때 얻는 운영 점수가 적혀 있다. 담당자는 인력 배치 계획에 맞추어 신청 중 정확히 K개를 승인하려 한다. 신청을 승인하면 적힌 시각 그대로 검사를 진행해야 하며, 시작이나 종료 시각을 옮길 수 없다. 검사실에서는 한 번에 하나의 검사만 진행할 수 있다. 또한 검사가 끝나면 다음 검사를 시작하기 전에 검사실을 정리하는 데 D만큼의 시간이 필요하다. 어떤 검사의 종료 시각이 e이고 그다음 검사의 시작 시각이 s이면, s가 e+D 이상일 때 두 검사를 차례로 진행할 수 있다. s가 e+D와 정확히 같아도 가능하다. 첫 검사 전과 마지막 검사 후에는 별도의 준비 시간을 확보할 필요가 없다. 예를 들어 D가 2이고 한 검사가 시각 6에 끝났다면 다음 검사는 시각 8부터 시작할 수 있다. 종료 시각과 다음 시작 시각이 같을 때 두 검사를 연속으로 진행할 수 있는 것은 D가 0인 경우뿐이다. 시각은 하루 안에서 비교하는 정수 값이며, 다음 날로 넘어가거나 시각이 순환하는 일은 없다. 각 신청은 독립적인 선택 대상이다. 서로 다른 신청의 시작 시각, 종료 시각, 운영 점수가 모두 같을 수도 있지만, 같은 신청을 두 번 승인할 수는 없다. 승인한 신청은 시작 시각 순서대로 진행하며, 어느 두 연속 검사 사이에서도 정리 시간 조건을 지켜야 한다. 신청이 입력되는 순서는 실제 검사 순서와 관계없다. 정확히 K개를 승인하면서 얻을 수 있는 운영 점수 합의 최댓값을 구하는 프로그램을 작성한다. 점수 합이 같은 승인 방법이 여러 개이면 그 공통 최댓값만 출력한다. 조건을 지키며 정확히 K개를 승인할 수 없다면 -1을 출력한다. K가 0이면 아무 신청도 승인하지 않는 방법이 가능하며, 이때 점수 합은 0이다.

입력

첫째 줄에 정수 N, K, D가 주어진다. 1≤N≤18, 0≤K≤N, 0≤D≤100이다.
다음 N개 줄에는 각 신청의 시작 시각 s, 종료 시각 e, 운영 점수 w가 정수로 주어진다. 0≤s<e≤10,000, 1≤w≤1,000,000이다.

출력

조건을 만족하는 승인 방법의 운영 점수 합 중 최댓값을 출력한다. 가능한 방법이 없으면 -1을 출력한다.

5 2 2
1 4 8
5 7 20
6 8 9
10 12 7
2 11 30

27

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

-1

2 0 3
1 2 7
4 8 12

0

출처: Devin.KR 자체 제작