P12247 跳舞机

小 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 想要最大化所有玩家的兴奋值之和，请你帮他求出最大的兴奋值之和。

无

无

#### 样例 #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$ | $L_i=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$ | $m\le 10^5$ | 无 | | $17\sim 20$ | $n\le 10^5$ | $m\le 10^5$ | $w_i=1$ | | $21,22$ | $n\le 10^5$ | $m\le 10^5$ | 无 | | $23\sim 25$ | $n\le 5\times 10^5$ | $m\le 5\times 10^5$ | 无 |