AT_kupc2019_f カズマ王国の陥落

[problemUrl]: https://atcoder.jp/contests/kupc2019/tasks/kupc2019_f カズマ王国には $ N $ 個の街があり、それぞれの街には $ 1 $ 人の勇者がいます。 $ i $ $ (1\ \leq\ i\ \leq\ N) $ 番目の街の勇者は合計して $ A_i $ 体までのモンスターを倒すことができます。 勇者は経験値が欲しいので、自分の街に来たモンスターはできるだけ多く倒します。 あなたは魔王で、$ M $ 個の拠点を支配下に置いています。 $ j $ $ (1\ \leq\ j\ \leq\ M) $ 番目の拠点からは合計 $ B_j $ 体のモンスターを自由に $ L_j,\ L_j+1,\ ...,\ R_j $ 番目の街に派遣します。 その結果、勇者に倒されなかったモンスターの数だけカズマ王国にダメージを与えることができます。 カズマ王国に与えられる合計ダメージの最大値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ A_2 $ $ ... $ $ A_N $ $ M $ $ L_1 $ $ R_1 $ $ B_1 $ $ L_2 $ $ R_2 $ $ B_2 $ $ \vdots $ $ L_M $ $ R_M $ $ B_M $

カズマ王国に与えられる合計ダメージの最大値を出力せよ。

### 制約 - 入力はすべて整数である。 - $ 1\ \leq\ N\ \leq\ 3000 $ - $ 1\ \leq\ M\ \leq\ 3000 $ - $ 1\ \leq\ A_i\ \leq\ 10^9 $ - $ 1\ \leq\ B_j\ \leq\ 10^9 $ - $ 1\ \leq\ L_j\ \leq\ R_j\ \leq\ N $ ### Sample Explanation 1 次のように派遣するとカズマ王国に合計して $ 7 $ ダメージを与えることができます。 - $ 1 $ 番目の拠点から $ 5 $ 体のモンスターを $ 2 $ 番目の街に、$ 2 $ 体のモンスターを $ 3 $ 番目の街にそれぞれ派遣します。 - $ 2 $ 番目の拠点から $ 4 $ 体のモンスターを $ 2 $ 番目の街に派遣します。 - $ 3 $ 番目の拠点から $ 3 $ 体のモンスターをそれぞれ $ 3 $ 番目の街に派遣します。 ### Sample Explanation 4 オーバーフローに気をつけてください。