레이팅 미적용JOI 氏は,自宅の敷地に N 本の木を所有している.これらの木は一列に並んでおり,順に 1 から N までの整数で番号が付けられている.
この冬,JOI 氏はいくつかの木を選んで,イルミネーションを飾り付けることにした.イルミネーションには 美しさ と呼ばれる値が定まっている.木 i にイルミネーションを飾り付ける場合の美しさは A_i である.
JOI 氏は,あまりに近い 2 つの木の両方にイルミネーションを飾り付けてしまうと,眩しすぎる場合があることに気がついた.具体的には, j = 1, 2, ..., M に対して,木 L_j , L_j + 1 , ... , R_j のうち 2 つ以上にイルミネーションを飾り付けるべきではないということが判明した.
この条件に従ってイルミネーションを飾り付けるときの,美しさの合計の最大値を求めよ.
\(1 \le N \le 200000\) (= 2×10^5)
\(1 \le M \le 200000\) (= 2×10^5)
1 ≦ A_i ≦ 1000000000 (= 10^9) ( \(1 \le i \le N\) )
1 ≦ L_j ≦ R_j ≦ N ( \(1 \le j \le M\) )
入力・出力
( 10 点) \(N \le 16\) , \(M \le 16\)
( 30 点) \(N \le 300\) , \(M \le 300\)
( 30 点) \(N \le 4000\) , \(M \le 4000\)
( 30 点) 追加の制限はない.
入力は以下の形式で標準入力から与えられる.
N M
A_1 A_2 ... A_N
L_1 R_1
L_2 R_2
⋮
L_M R_M
イルミネーションの美しさの合計の最大値を 1 行で出力せよ.
4 1
1 2 3 8
2 4
9
5 2
2 3 9 5 6
1 3
2 4
15
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
4912419478