Description

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.

Input Format

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 Format

Output a single integer - the maximum total excitement possible.

3 6 2
1 5 1
5 6 2
5 6 3

5

4 7 3
1 7 1
2 5 4
4 7 5
1 2 10

9

Hint

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: