P12520 「MSTOI-R1」超速检测II

以此纪念某位七年级参加 NOIP，八年级挂在 CSP-S T2 的大佬。

小 D 新入职了某国的交管部门，他的第一个任务是负责国家的一条长度为 $L$ 的南北主干道的车辆超速检测。为了考考小 D，小 W 制造了一辆速度为 $ \infty $ 的汽车（这真的是汽车吗？），因此从点 $i$ 到点 $i+1$ 的时间可以为 $0$。 每一天早上，小 W 的车将会出现在主干道上，并从主干道上最南端 $1$ 号点的位置驶入向北行驶至最北端的 $n$ 号点。主干道上设置了 $m$ 组测速仪，其中第 $i$ 组测速仪测量主干道上任意一辆车从点 $l_i$ 到点 $r_i$ 所花费的时间。若这辆车的所花时间**小于**道路限制时间 $V_i$，那么这辆车就会被判定为超速。 然而，交通部门的政策总是朝令夕改。每天交通部门都会在凌晨增加或修改一条限制并在每天晚上将其删除或改回。~~为了睡懒觉，~~ 小 W 每天都会计算从 $ 1 $ 点到 $ n $ 点所需的最短时间。 由于 $n$ 很大，小 W 想要使用编程解决这个问题，然而他不会，于是小 W 找到了你。

无

无

对于 $20\%$ 的数据，$1\le n,m\le 100$，$1\le d\le 20$，$1\le V_i\le1000$。 对于 $50\%$ 的数据，$1\le n,m\le 1000$，$1\le d\le 1000$，$1\le V_i\le10^5$。 对于 $100\%$ 的数据，$1\le l_i