착유 시간

베시(Bessie)는 매우 성실한 젖소로, 우유 생산량을 최대로 늘리고 싶어 한다. 베시는 앞으로의 $N$ ($1 \le N \le 10^6$)시간을 $0 \dots N-1$로 번호를 매겨 계획하며, 이 시간 동안 가능한 한 많은 우유를 생산하려 한다.

농부 존(Farmer John)은 착유가 가능한 $M$ ($1 \le M \le 1000$)개의 구간 목록을 가지고 있으며, 이 구간들은 서로 겹칠 수 있다. $i$번째 구간은 시작 시각 $s_i$ ($0 \le s_i < N$), 종료 시각 $e_i$ ($s_i < e_i \le N$), 그리고 효율 $w_i$ ($1 \le w_i \le 10^6$)로 이루어지며, $w_i$는 그 구간 동안 베시가 생산하는 우유의 갤런 수이다. 착유는 시작 시각의 시작에 시작되어 종료 시각의 시작에 끝난다. 베시는 한 구간에서 착유를 시작하면 반드시 그 구간 전체 동안 착유되어야 한다.

어떤 구간에서 착유된 뒤, 베시는 다시 착유를 시작하기 전에 $R$ ($1 \le R \le N$)시간 동안 쉬어야 한다. 즉, 종료 시각이 $e$인 구간에서 착유되었다면, 다음으로 착유되는 구간은 시각 $e + R$ 이후(그 시각 포함)에 시작해야 한다. 주어진 구간 목록을 바탕으로, 베시가 $N$시간 동안 생산할 수 있는 우유의 최대 갤런 수를 구하여라.

• 첫째 줄: 공백으로 구분된 세 정수 $N$, $M$, $R$.
• 둘째 줄부터 $M+1$째 줄까지: $i+1$째 줄은 $i$번째 착유 구간을 공백으로 구분된 세 정수 $s_i$, $e_i$, $w_i$로 나타낸다.

• 첫째 줄: 베시가 $N$시간 동안 생산할 수 있는 우유의 최대 갤런 수.