題目描述

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