O - 宝箱 Editorial /

Time Limit: 5 sec / Memory Limit: 1024 MB

配点 : 6 点

注意

この問題に対する言及は、2020/11/8 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

あなたは 1 から N の番号がついた N 個の宝箱を見つけました。 はじめ、全ての宝箱は施錠されており開けることはできません。 宝箱 i を解錠すると、あなたは a_i 円を得ることができます。

あなたには 1 から M の番号がついた M 人の鍵屋の友人がいます。 鍵屋 i に c_i 円を払って解錠を依頼すると、宝箱 l_i, l_i + 1, \ldots, r_i のうち、まだ施錠されている宝箱全てが解錠されます。

あなたの目的は、鍵屋に支払った金額の総和を X、解錠された宝箱から得た金額の総和を Y として Y-X を最大化することです。Y-X としてありうる値の最大値を求めてください。

制約

  • 与えられる入力は全て整数
  • 1 \leq N,M \leq 2 \times 10^5
  • 1 \leq a_i,c_i \leq 10^9
  • 1 \leq l_i \leq r_i \leq N

入力

入力は以下の形式で標準入力から与えられる。

N M
a_1 a_2 \cdots a_N
l_1 r_1 c_i
\vdots
l_M r_M c_M

出力

鍵屋に支払った金額の総和を X、解錠された宝箱から得た金額の総和を Y として Y-X としてありうる値の最大値を出力せよ。

入力例 1

4 3
20 10 100 10
1 3 100
2 4 50
1 1 50

出力例 1

70
  • 鍵屋 2 に 50 円払い、宝箱 2,3,4 を解錠して 10+100+10=120 円を得るのが最適です。
  • 全ての宝箱を解錠する必要がないことに注意してください。

入力例 2

2 2
10 10
1 1 1000
1 2 100

出力例 2

0
  • どの鍵屋にも解錠を依頼しないのが最適な場合がありうることに注意してください。

入力例 3

20 10
40 28 12 29 34 89 37 64 48 53 81 95 46 42 77 76 49 59 14 15
2 11 221
14 20 14
2 11 126
1 8 273
5 11 94
2 8 48
12 15 83
2 7 13
5 16 269
3 12 115

出力例 3

760

Score : 6 points

Warning

Do not make any mention of this problem until November 8, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

You have found N treasure chests numbered 1 through N. Initially, all the chests are locked and cannot be opened. If you manage to unlock Chest i, you get a_i yen (the currency of Japan).

Among your friends, there are M locksmiths, numbered 1 through M. If you ask Locksmith i to unlock chests by paying c_i yen, the locksmith will unlock all chests that are still locked among the chests l_i, l_i + 1, \ldots, r_i.

Your objective is to maximize Y-X, where X is the total amount of money you pay to locksmiths, and Y is the total amount of money you get from chests. Find the maximum possible value of Y-X.

Constraints

  • All values in input are integers.
  • 1 \leq N,M \leq 2 \times 10^5
  • 1 \leq a_i,c_i \leq 10^9
  • 1 \leq l_i \leq r_i \leq N

Input

Input is given from Standard Input in the following format:

N M
a_1 a_2 \cdots a_N
l_1 r_1 c_i
\vdots
l_M r_M c_M

Output

Print the maximum possible value of Y-X, where X is the total amount of money you pay to locksmiths, and Y is the total amount of money you get from chests.

Sample Input 1

4 3
20 10 100 10
1 3 100
2 4 50
1 1 50

Sample Output 1

70
  • It is optimal to pay 50 yen to Locksmith 2 and get 10+100+10=120 yen from unlocking the chests 2,3,4.
  • Note that you do not have to unlock all the chests.

Sample Input 2

2 2
10 10
1 1 1000
1 2 100

Sample Output 2

0
  • Note that the optimal strategy might be not asking any locksmiths to unlock chests.

Sample Input 3

20 10
40 28 12 29 34 89 37 64 48 53 81 95 46 42 77 76 49 59 14 15
2 11 221
14 20 14
2 11 126
1 8 273
5 11 94
2 8 48
12 15 83
2 7 13
5 16 269
3 12 115

Sample Output 3

760