문제
JOI 씨는 집 터에 나무 \(N\)그루를 가지고 있다. 나무는 한 줄로 늘어서 있고, 차례로 \(1\)부터 \(N\)까지 번호가 붙어 있다. 이번 겨울 JOI 씨는 몇 그루를 골라 일루미네이션을 달기로 했다. 일루미네이션에는 아름다움이라는 값이 정해져 있다. 나무 \(i\)에 일루미네이션을 달 때의 아름다움은 \(A_i\)이다. 너무 가까운 두 나무에 모두 일루미네이션을 달면 눈이 부신 경우가 있다. 구체적으로, \(j = 1, 2, \ldots, M\)에 대해 나무 \(L_j, L_j+1, \ldots, R_j\) 가운데 \(2\)그루 이상에 일루미네이션을 달면 안 된다. 이 조건을 지키며 일루미네이션을 달 때, 아름다움 합의 최댓값을 구하는 프로그램을 작성하라. |
입력
입력은 다음 형식으로 주어진다.
\(N\) \(M\)
\(A_1\) \(A_2\) \(\cdots\) \(A_N\)
\(L_1\) \(R_1\)
\(L_2\) \(R_2\)
\(\vdots\)
\(L_M\) \(R_M\)
- 첫째 줄에 나무의 수 \(N\)과 제약의 수 \(M\)이 공백 하나로 구분되어 주어진다.
- 둘째 줄에 \(N\)개의 정수 \(A_1, A_2, \ldots, A_N\)이 공백 하나로 구분되어 주어진다.
- 다음 \(M\)줄의 \(j\)번째 줄에 정수 \(L_j\)와 \(R_j\)가 공백 하나로 구분되어 주어진다.
- \(1 \le N \le 200000\)
- \(1 \le M \le 200000\)
- \(1 \le A_i \le 1000000000\)
- \(1 \le L_j \le R_j \le N\)
- 입력되는 값은 모두 정수이다.
출력
다음 형식으로 출력한다.
첫째 줄에 일루미네이션 아름다움 합의 최댓값을 출력한다.
예시 1
입력
4 1
1 2 3 8
2 4
출력
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
출력
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
출력
4912419478