AT_joi2019_yo_e イルミネーション (Illumination)

[problemUrl]: https://atcoder.jp/contests/joi2019yo/tasks/joi2019_yo_e JOI 氏は，自宅の敷地に $ N $ 本の木を所有している．これらの木は一列に並んでおり，順に $ 1 $ から $ N $ までの整数で番号が付けられている． この冬，JOI 氏はいくつかの木を選んで，イルミネーションを飾り付けることにした．イルミネーションには**美しさ**と呼ばれる値が定まっている．木 $ i $ にイルミネーションを飾り付ける場合の美しさは $ A_i $ である． JOI 氏は，あまりに近い $ 2 $ つの木の両方にイルミネーションを飾り付けてしまうと，眩しすぎる場合があることに気がついた．具体的には，$ j\ =\ 1,\ 2,\ ...,\ M $ に対して，木 $ L_j $, $ L_j\ +\ 1 $, $ ... $, $ R_j $ のうち $ 2 $ つ以上にイルミネーションを飾り付けるべきではないということが判明した． この条件に従ってイルミネーションを飾り付けるときの，美しさの合計の最大値を求めよ．

入力は以下の形式で標準入力から与えられる． > $ N $ $ M $ $ A_1 $ $ A_2 $ $ ... $ $ A_N $ $ L_1 $ $ R_1 $ $ L_2 $ $ R_2 $ $ ⋮ $ $ L_M $ $ R_M $

イルミネーションの美しさの合計の最大値を $ 1 $ 行で出力せよ．

### 制約 - $ 1\ ≦\ N\ ≦\ 200000\ (=\ 2×10^5) $ - $ 1\ ≦\ M\ ≦\ 200000\ (=\ 2×10^5) $ - $ 1\ ≦\ A_i\ ≦\ 1000000000\ (=\ 10^9) $ ($ 1\ ≦\ i\ ≦\ N $) - $ 1\ ≦\ L_j\ ≦\ R_j\ ≦\ N $ ($ 1\ ≦\ j\ ≦\ M $) ### 小課題 1. ($ 10 $ 点) $ N\ ≦\ 16 $，$ M\ ≦\ 16 $ 2. ($ 30 $ 点) $ N\ ≦\ 300 $，$ M\ ≦\ 300 $ 3. ($ 30 $ 点) $ N\ ≦\ 4000 $，$ M\ ≦\ 4000 $ 4. ($ 30 $ 点) 追加の制限はない． ### Sample Explanation 1 この入力例では，木 $ 1 $, $ 4 $ にイルミネーションを飾り付けると，美しさの合計が $ 9 $ となり最大となる．$ L_1\ =\ 2 $, $ R_1\ =\ 4 $ なので，木 $ 2 $, $ 3 $, $ 4 $ のうち $ 2 $ つ以上にイルミネーションを飾り付けることはできない．例えば木 $ 1 $, $ 2 $, $ 4 $ にイルミネーションを飾り付けることはできないことに注意せよ．