← 返回题目列表

AtCoder · xmascon16_g

G. 引导乘客

中文机器翻译题面 查看原题

配点 : 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