16789번 - イルミネーション (Illumination) 서브태스크다국어

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)