P16692 染色 Plus

小 G 有一个 $1 \times N$ 的网格条带和 $M$ 种颜料，每种颜料在第 $[L_i,R_i]$ 格内可用，涂一格需要花费 $C_i$ 的代价。 现在，小 G 想在每一格内都涂上一种可用的颜料。小 G 希望这个网格条带内颜色尽量丰富，所以任意连续 $K$ 格内的颜色不能全部相同。小 G 想知道，涂色的总代价最小是多少？如果不存在满足条件的染色方式，输出 $-1$.

第一行，三个整数 $N,M,K$，如题中所述。 接下来 $M$ 行，每行三个整数 $L_i,R_i,C_i$，如题中所述。

一个整数，表示答案。

**【样例解释】** 对于第一组数据，第 $1-10$ 格分别涂第 $1,2,2,3,3,6,3,6,6,4$ 种颜料，总代价为 $3+2+2+4+4+1+4+1+1+6=28$，可以证明这是满足条件的最小代价。 对于第二组数据，由于第 $10$ 格没有颜料可用，因此不存在满足条件的染色方式，输出 $-1$。 **【数据范围】** 对于 $100 \%$ 的数据，$2 \le N,M \le 2 \times 10^5$，$2 \le K \le N$， $1 \le L_i \le R_i \le N$， $1 \le C_i \le 10^9$。