시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 1 1 1 100.000%

문제

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

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