Skip to content
Sign in

イルミネーション (Illumination)

Unrated
日本語

Language

Contribute a translation
Time limit
2000 ms
Memory limit
256 MB
Submissions
0
Correct
0
Solved by
0
AC rate
—

Statement

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

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

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

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

Constraints

  • \(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\))

Input

入力は以下の形式で標準入力から与えられる．

\(N\) \(M\)
\(A_1\) \(A_2\) \(...\) \(A_N\)
\(L_1\) \(R_1\)
\(L_2\) \(R_2\)
\(⋮\)
\(L_M\) \(R_M\)

Output

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

Subtasks

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

Examples

Sample input 1
4 1
1 2 3 8
2 4
Sample output 1
9

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

Sample input 2
5 2
2 3 9 5 6
1 3
2 4
Sample output 2
15
Sample input 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
Sample output 3
4912419478

Notes

JOI 2019 · JCIOI · CC BY-SA 4.0

Tags

No tags yet

Source