일루미네이션

문제

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\,\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$)

서브태스크

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$ 점) 추가 제한이 없다.

입력과 출력

입력
입력은 다음 형식으로 표준 입력으로부터 주어진다.
$N$ $M$
$A_1$ $A_2$ $...$ $A_N$
$L_1$ $R_1$
$L_2$ $R_2$
$⋮$
$L_M$ $R_M$

출력
일루미네이션의 아름다움의 합의 최댓값을 $1$ 줄로 출력한다.

예제 입력 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