P12247 Dance Machine

Little O wants to operate an arcade, where the dance machine's operation is crucial. There is one dance machine in Little O's arcade that can accommodate **at most one player at any given time**. Each game session requires a complete and continuous playtime of exactly $k$ minutes. The venue will be open for $m$ minutes. During this period, $n$ players want to use the dance machine, numbered from $1$ to $n$. Player $i$ will be present from minute $l_i$ to minute $r_i$ (inclusive) and can play any number of complete game sessions during their stay. Each completed session generates $w_i$ excitement points. Note that for player $i$ to play a session, the entire $k$-minute duration must be fully contained within their stay interval $[l_i, r_i]$. Little O wants to maximize the total excitement points from all players. Your task is to determine the maximum possible total excitement.

The input consists of $n+1$ lines: - Line $1$: Three integers $n$, $m$, $k$ - number of players, operating duration, and session length. - Lines $2$ to $n+1$: Each line contains three integers $l_i$, $r_i$, $w_i$ - the stay interval and excitement per session for player $i$.

Output a single integer - the maximum total excitement possible.

### Sample #1 Explanation Optimal schedule: - Player $1$ plays at $[1,2]$ and $[3,4]$。 - Player $3$ plays at $[5,6]$。 Total: $1\times 2 + 3\times 1 = 5$ points (maximum possible) ### Sample #2 Explanation Optimal schedule: - Player $2$ plays at $[2,4]$。 - Player $3$ plays at $[5,7]$。 Total: $4 + 5 = 9$ points (maximum possible) ## Constraints - $1\le n,m,k\le 5\times 10^5$ ； - $k\le m$； - $1\le l_i\le r_i\le m$； - $1\le w_i\le 10^9$。 Let $L_i = r_i - l_i + 1$. Subtask constraints: | Test Case | $n$ Range | $m$ Range | Special Properties | | :----------: | :----------: | :----------: | :----------: | | $1\sim 3$ | $n\le 5$ | $m\le 10$ | $w_i\le 20$ | | $4\sim 6$ | $n\le 10^5$ | $m\le 10^5$ | $L_i=k=1$ | | $7\sim10$ | $n\le 1000$ | $m\le 1000$ | None | | $11\sim 13$ | $n\le 10^5$ | $m\le 10^5$ | $L_i=k$ | | $14\sim 16$ | $n\le 100$ | $m\le 10^5$ | None | | $17\sim 20$ | $n\le 10^5$ | $m\le 10^5$ | $w_i=1$ | | $21,22$ | $n\le 10^5$ | $m\le 10^5$ | None | | $23\sim 25$ | $n\le 5\times 10^5$ | $m\le 5\times 10^5$ | None |