問題文

JOI 氏は，自宅の敷地に $N$ 本の木を所有している．これらの木は一列に並んでおり，順に $1$ から $N$ までの整数で番号が付けられている．

この冬，JOI 氏はいくつかの木を選んで，イルミネーションを飾り付けることにした．イルミネーションには美しさと呼ばれる値が定まっている．木 $i$ にイルミネーションを飾り付ける場合の美しさは $A_i$ である．

JOI 氏は，あまりに近い $2$ つの木の両方にイルミネーションを飾り付けてしまうと，眩しすぎる場合があることに気がついた．具体的には，$j = 1, 2, \dots, M$ に対して，木 $L_j$, $L_j + 1$, $\dots$, $R_j$ のうち $2$ つ以上にイルミネーションを飾り付けるべきではないということが判明した．

この条件に従ってイルミネーションを飾り付けるときの，美しさの合計の最大値を求めよ．

制約

• $1 \le N \le 200000 (= 2 \times 10^5)$
• $1 \le M \le 200000 (= 2 \times 10^5)$
• $1 \le A_i \le 1000000000 (= 10^9)$ ($1 \le i \le N$)
• $1 \le L_j \le R_j \le N$ ($1 \le j \le M$)

入力・出力

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

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

小課題

1. ($10$ 点) $N \le 16$，$M \le 16$
2. ($30$ 点) $N \le 300$，$M \le 300$
3. ($30$ 点) $N \le 4000$，$M \le 4000$
4. ($30$ 点) 追加の制限はない．

入出力例

入力例 1

4 1
1 2 3 8
2 4

出力例 1

9

この入力例では，木 $1$, $4$ にイルミネーションを飾り付けると，美しさの合計が $9$ となり最大となる．$L_1 = 2$, $R_1 = 4$ なので，木 $2$, $3$, $4$ のうち $2$ つ以上にイルミネーションを飾り付けることはできない．例えば木 $1$, $2$, $4$ にイルミネーションを飾り付けることはできないことに注意せよ．

入力例 2

5 2
2 3 9 5 6
1 3
2 4

出力例 2

15

入力例 3

20 10
870851814 594414687 615919461 65033245 460143082 617460823 881870957 126041265 623075703 34130727 27054628 853567651 483228744 491145755 220689940 148007930 229257101 790404982 612186806 281076231
15 19
20 20
12 13
1 4
19 19
9 13
3 6
9 12
16 16
18 19

出力例 3

4912419478