Maximizing Excitement on the Dance Machine

In Electric Van City, there is a popular dance machine whose operation is critical for the business. At any given time, at most one player can use the dance machine, and each game lasts exactly $k$ consecutive minutes. The van city operates for $m$ minutes per day. There are $n$ players numbered from $1$ to $n$. The $i$-th player remains in the city from minute $l_i$ to minute $r_i$ (inclusive) and can play any number of games provided that each game is completely played within their time interval. Each completed game played by the $i$-th player contributes an excitement value of $w_i$. When a game is scheduled at time $s$, it occupies the interval $[s, s+k-1]$. A player $i$ can only participate in that game if and only if ( l_i \le s ) and ( s+k-1 \le r_i ). Games must not overlap. Your task is to design a schedule (i.e. select starting times for some game sessions) such that the total excitement value is maximized.

inputFormat

The first line of input contains three integers (n), (m), and (k). Each of the following (n) lines contains three space-separated integers (l_i), (r_i), and (w_i), describing the arrival time, departure time, and excitement value for the (i)-th player.

outputFormat

Output a single integer: the maximum total excitement value that can be achieved by scheduling non-overlapping game sessions.

sample

3 20 5
1 10 3
6 20 4
12 20 5

16