题目描述

小 O 想要经营电 van 城，跳舞机的运营非常重要。

小 O 的电 van 城有一台跳舞机，跳舞机在同一时间至多有一名玩家游玩，每局游戏需要完整且连续地游玩 $k$ 分钟。

电 van 城将营业 $m$ 分钟。期间有 $n$ 名玩家想要游玩跳舞机，编号 $1\sim n$。编号为 $i$ 的玩家会在营业的第 $l_i$ 分钟到第 $r_i$ 分钟（包括 $l_i$ 和 $r_i$）待在电 van 城，在此期间可以游玩任意局跳舞机。并且，每游玩一局，会产生 $w_i$ 的兴奋值。注意，如果玩家 $i$ 要玩一局跳舞机，则每局游戏的 $k$ 分钟必须完全包含于玩家的停留时间 $[l_i,r_i]$。

小 O 想要最大化所有玩家的兴奋值之和，请你帮他求出最大的兴奋值之和。

输入格式

输入共 $n+1$ 行。

第一行输入三个整数 $n,m,k$，分别表示玩家个数、营业时间、游玩一局跳舞机需要的时间。

第 $2\sim n+1$ 行，第 $i+1$ 行有三个整数 $l_i,r_i,w_i$，表示编号为 $i$ 的玩家的停留时间和游玩一局产生的兴奋值。

输出格式

输出共一行一个整数，表示最大的兴奋值之和。

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

提示

样例 #1 解释

可以让编号为 $1$ 的玩家在第 $1\sim2$ 分钟、第 $3\sim 4$ 分钟玩一局跳舞机，编号为 $3$ 的玩家在第 $5\sim 6$ 分钟玩一局。兴奋值的总和为 $1+1+3=5$，可以发现没有让兴奋值总和更大的方案。

样例 #2 解释

可以让编号为 $2$ 的玩家在第 $2\sim4$ 分钟玩一局跳舞机，编号为 $3$ 的玩家在第 $5\sim 7$ 分钟玩一局。兴奋值的总和为 $4+5=9$，可以发现没有让兴奋值总和更大的方案。

数据范围

对于所有数据，满足：

• $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$。

设 $L_i=r_i-l_i+1$，则具体测试点限制如下：

测试点编号	$n$ 的范围	$m$ 的范围	特殊性质
$1\sim 3$	$n\le 5$	$m\le 10$	$w_i\le 20$
$4\sim 6$	$n\le 10^5$	$m\le 10^5$	$k=1$
$7\sim10$	$n\le 1000$	$m\le 1000$	无
$11\sim 13$	$n\le 10^5$	$m\le 10^5$	$L_i=k$
$14\sim 16$	$n\le 100$		无
$17\sim 20$	$n\le 10^5$		$w_i=1$
$21,22$			无
$23\sim 25$	$n\le 5\times 10^5$	$m\le 5\times 10^5$