問題文

うさ鉄道は，うさぎのための鉄道である．うさ鉄道には東西に伸びる 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 に運ぶことが出来るだろうか？

制約

• 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 を満たすようなものは存在しない．
  • つまり，追い越しは発生せず，同時刻に同じ駅を出発する列車の組や，同時刻に同じ駅に到着する列車の組は存在しない．

入力例 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