配点 : 100 点
問題文
兔子铁路是为兔子而建的铁路。兔子铁路有东西方向延伸的 1 很长的线路和 N 个车站。车站从西向东按顺序编号。 1~N 每个车站有容量,车站 i\ (1 \leq i \leq N) 可以同时 C_i 只能存在到羽毛的程度。
在兔子铁路 M 计划运行真正的列车,列车 i\ (1 \leq i \leq M) 在时间 S_i 到达车站 A_i 出发,于 T_i 到达车站 A_i+1 到达的列车,能够载运B_i 只兔子。由于兔铁路的线路只有 1 条,因此为了避免发生超车,列车的发车和到达时间是预先确定的。此外,不会存在同时刻从同一车站出发的列车组,也不会存在同时刻到达同一车站的列车组。但是,在某一时刻,可能存在从某个车站出发的列车与同时到达同一车站的列车。在这种情况下,不论车站容量如何,在列车出发之前,乘降可以自由进行,兔子数量不限。共有
今,駅 1 向 C_1 只兔子,全体在车站 N 。当巧妙地运送兔子而不超过各车站的容量时,最多可以将多少只兔子运送到车站 N ?符合
制約
- 2 \leq N \leq 500,000.
- 0 \leq M \leq 500,000.
- 1 \leq C_i,\ B_i \leq 10^9.
- 1 \leq S_i \lt T_i \leq 10^9.
- 1 \leq A_i \leq N-1.
- A_i = A_j 的 i,\ j\ (i \neq j) ,S_i \leq S_j 和 T_i \geq T_j 满足的东西不存在。
- 也就是说,不会发生超车,同时刻从同一车站出发的列车组,以及同时刻到达同一车站的列车组都不会发生。
入力
输入是按以下格式从标准输入给出的。
N M C_1 C_2 ... C_N S_1 T_1 A_1 B_1 S_2 T_2 A_2 B_2 : S_M T_M A_M B_M
出力
駅 N 输出能够运输的兔子的最大羽数。
入力例 1
3 4 9 2 9 1 2 1 3 2 3 2 4 6 9 2 5 2 4 1 5
出力例 1
5
如下所示 5 能运送羽毛兔。
- 列車 1 向 3 骑在羽毛上。
- 駅 2 在火车站 2 全员换乘。
- 駅 3 在...全部下车。
- 列車 4 向 2 骑在羽毛上。
- 駅 2 全员下车后在...等待列车。 3 等列车。
- 列車 3 全员乘坐。
- 駅 3 在...全部下车。
入力例 2
3 2 1 9 9 1 2 1 5 3 4 2 5
出力例 2
1
入力例 3
2 1 1000000000 2016 999999999 1000000000 1 1000000000
出力例 3
2016
入力例 4
2 0 12 24
出力例 4
0
入力例 5
4 11 8 2 3 9 1 2 1 1 2 4 1 1 4 5 1 6 6 7 1 1 6 7 2 3 5 6 2 5 3 4 2 3 4 6 3 2 6 7 3 1 7 8 3 4 8 9 3 2
出力例 5
7