아우토반

시간 제한1초메모리 제한512 MB

요약

각 운전자가 정해진 시간 구간 동안 머무르고, 동시에 K명 이상이 있는 분에 초과 요금이 부과될 때, 연속한 X분을 면제 구간으로 골라 면제되는 요금 합의 최댓값을 구한다.

난이도: 어려움10점 중 8점
유형: 누적 합, 슬라이딩 윈도우, 정렬, 구현
정답자: 아직 제출이 없습니다

문제

한계 속도가 없는 악명 높은 아우토반에서 $N$ 명이 자신의 경주차를 시험하고 있다. 하지만 이 문제에는 한계가 있다. 그러니 지수 시간 복잡도 풀이를 제출하는 것은 삼가 주기를 정중히 부탁한다.

$i$ 번째 사람은 $l_i$ 분이 시작될 때 아우토반에 와서 $t_i$ 분만큼의 체류 시간을 지불하고 $r_i$ 분이 끝날 때 떠났다. 안타깝게도 몇몇은 지불한 시간보다 더 오래 머물렀다. 아우토반 관리소는 너무 엄격하게 굴지 않기로 하고, 아우토반에 최소 $K$ 명이 있는 추가 시간에 대해서만 요금을 부과하기로 했다.

관리소는 관대함을 베풀어 해피 아워를 도입하기로 했다. 즉, 추가 요금을 부과하지 않는 연속한 $X$ 분의 구간이다. 이들은 면제되는 추가 요금의 합이 최대가 되도록 해피 아워를 골랐다. 그 합을 구하라.

입력

첫 줄에는 문제 설명에 나온 정수 $N$ , $K$ , $X$ 가 주어진다 ( $K \le N$ ).

다음 $N$ 개 줄에는 문제 설명에 나온 정수 $l_i$ , $t_i$ , $r_i$ 가 주어진다 ( $l_i \le r_i$ ).

출력

구한 합을 한 줄에 출력한다.

힌트

첫 번째 예제 설명: 해피 아워는 4분부터 7분까지 이어진다. 그 구간에서 첫 번째 사람은 4분에 대한 추가 요금을 내야 하고, 두 번째, 세 번째, 네 번째 사람은 6분과 7분에 대한 요금을 내야 한다.

예제2

예제 1
입력
```
5 3 4
2 1 4
3 3 7
3 3 8
1 5 7
5 3 8
```
예상 출력
```
7
```
예제 2
입력
```
3 2 22
7 16 33
69 14 88
8 10 97
```
예상 출력
```
27
```