AT_past202010_o 宝箱

[problemUrl]: https://atcoder.jp/contests/past202010-open/tasks/past202010_o あなたは $ 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 $ としてありうる値の最大値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ 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 $ としてありうる値の最大値を出力せよ。

### 注意 この問題に対する言及は、2020/11/8 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。 ### 制約 - 与えられる入力は全て整数 - $ 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 $ ### Sample Explanation 1 \- 鍵屋 $ 2 $ に $ 50 $ 円払い、宝箱 $ 2,3,4 $ を解錠して $ 10+100+10=120 $ 円を得るのが最適です。 - 全ての宝箱を解錠する必要がないことに注意してください。 ### Sample Explanation 2 \- どの鍵屋にも解錠を依頼しないのが最適な場合がありうることに注意してください。