일루미네이션
시간 제한2초메모리 제한512 MB
M개의 구간 각각에서 장식한 나무가 최대 하나가 되도록 나무의 부분집합을 골라 아름다움 합의 최댓값을 구한다.
문제
JOI씨는 자택 부지에 N그루의 나무를 가지고 있다. 이 나무들은 한 줄로 늘어서 있고, 순서대로 1부터 N까지의 정수가 붙어 있다.
올겨울 JOI씨는 몇 그루의 나무를 골라 일루미네이션을 장식하기로 했다. 일루미네이션에는 아름다움이라는 값이 정해져 있다. 나무 i에 일루미네이션을 장식할 때의 아름다움은 A_i이다.
JOI씨는 너무 가까운 두 나무에 모두 일루미네이션을 장식하면 눈이 부실 수 있다는 것을 깨달았다. 구체적으로, j = 1, 2, ..., M에 대해 나무 L_j, L_j + 1, ..., R_j 중 두 그루 이상에 일루미네이션을 장식해서는 안 된다는 사실이 밝혀졌다.
이 조건에 따라 일루미네이션을 장식할 때, 아름다움 합의 최댓값을 구하시오.
입력
입력은 다음 형식으로 표준 입력에서 주어진다.
N M
A_1 A_2 ... A_N
L_1 R_1
L_2 R_2
⋮
L_M R_M
출력
일루미네이션의 아름다움 합의 최댓값을 1행으로 출력하시오.
제한
- 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)