Problem Description

Xiao G has a $1 \times N$ grid strip and $M$ types of paint. Each type of paint can be used on cells in the interval $[L_i, R_i]$, and painting one cell costs $C_i$.

Now, Xiao G wants to paint every cell with one available type of paint. Xiao G wants the colors on this grid strip to be as diverse as possible, so in any $K$ consecutive cells, the colors cannot all be the same. Xiao G wants to know the minimum total cost of painting. If there is no coloring method that satisfies the condition, output $-1$.

Input Format

The first line contains three integers $N, M, K$, as described above.

The next $M$ lines each contain three integers $L_i, R_i, C_i$, as described above.

Output Format

Output one integer, representing the answer.

10 6 3
1 2 3
1 3 2
4 7 4
1 10 6
1 10 7
6 9 1

28

10 5 3
1 2 3
1 3 2
4 7 4
5 9 6
6 9 1

-1

Hint

Sample Explanation

For the first test case, cells $1$ to $10$ are painted with paint types $1, 2, 2, 3, 3, 6, 3, 6, 6, 4$ respectively. The total cost is $3+2+2+4+4+1+4+1+1+6=28$. It can be proven that this is the minimum cost that satisfies the condition.

For the second test case, since cell $10$ has no available paint, there is no coloring method that satisfies the condition, so output $-1$.

Constraints

For $100\%$ of the testdata, $2 \le N, M \le 2 \times 10^5$, $2 \le K \le N$, $1 \le L_i \le R_i \le N$, and $1 \le C_i \le 10^9$.

Translated by ChatGPT 5