AT_xmascon16_g Guide Passengers

[problemUrl]: https://atcoder.jp/contests/xmascon16noon/tasks/xmascon16_g うさ鉄道は，うさぎのための鉄道である．うさ鉄道には東西に伸びる $ 1 $ 本の長い線路と $ N $ 個の駅がある．駅には西から順に $ 1～N $ の番号が付けられている．各駅には capacity があり，駅 $ 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 $ 本しかないため，追い越しが発生しないように列車の発着時刻を決めている．また，同時刻に同じ駅を出発する列車の組や，同時刻に同じ駅に到着する列車の組は存在しない．ただし，ある時刻にある駅を出発する列車と同時刻に同じ駅を到着する列車が存在することはある．この場合，駅の capacity によらず，列車が発車するまでは乗り降りを何羽でも自由に行うことが出来る． 今，駅 $ 1 $ に $ C_1 $ 羽のうさぎがおり，全員が駅 $ N $ に向かおうとしている．各駅の capacity を超えないようにうまくうさぎを運んだとき，最大で何羽のうさぎを駅 $ N $ に運ぶことが出来るだろうか？

入力は以下の形式で標準入力から与えられる． > $ 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 $ に運ぶことの出来るうさぎの羽数の最大値を出力せよ．

### 制約 - $ 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 $ で全員降りる．