AT_xmascon16_g Guide Passengers

## 题目意思 兔子铁路是兔子专用的铁路。车站从西到右依次编号为1～N（1≤i≤N）。各站都有限制C，车站只能同时有Ci只兔子等车。 铁道计划运行M（1≤i≤M）趟列车，列车是在时刻Si从车站Ai出发，在时刻Ti到达车Ai+1，只可以搭载兔子Bi只。 现在，车站1有一只C1的兔子，所有兔子都想去车站N，最多能搬运几只兔子到车站N？ ## 样例1解释 可以像以下那样搬运5只兔子。 -列车1乘坐3只。 -在车站2全体换乘列车2（到站时另一辆列车--2号车恰好来了，所以不考虑车站2的限制。 -在车站3全体下车。 -列车4乘坐5只。 -在车站2全体下车等待列车3（3号车还没到，所以要等车，考虑限制为C2--2只兔子，所以5只兔子只留了2只等车，剩下的可以不用运过来，放回车站1）。 -剩下的两只乘坐列车3。 -在车站3全体下车。 共计5只兔子来到n站。

第一行两个整数 $N$ $M$，表示车站数和列车数。 第二行$N$个整数 $C1...Cn$ ,表示每个车站的限制。 接下来$M$组数据： $S,T,A,B$。

一个整数$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 $ を満たすようなものは存在しない． - つまり，追い越しは発生せず，同時刻に同じ駅を出発する列車の組や，同時刻に同じ駅に到着する列車の組は存在しない． ### Sample Explanation 1 以下のように $ 5 $ 羽のうさぎを運ぶことが出来る． - 列車 $ 1 $ に $ 3 $ 羽乗る． - 駅 $ 2 $ で列車 $ 2 $ に全員が乗り換える． - 駅 $ 3 $ で全員降りる． - 列車 $ 4 $ に $ 2 $ 羽乗る． - 駅 $ 2 $ で全員降りて列車 $ 3 $ を待つ． - 列車 $ 3 $ に全員乗る． - 駅 $ 3 $ で全員降りる．