문제 설명

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