Informatica Online Judge

  조명 [2331 / 091B]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 9   Total Tried : 12


The Champion of this Problem (C++) : gs18081 - ms / 625byte
My Best Submission (C++) : N/A

[2019 JOI 예선]

Background

경곽이는 집의 마당에 n개의 나무가 있다. 이들 나무는 한 줄로 되어 있으며 순서대로 1부터 n까지의 번호가 부여되어 있다.

이번 겨울에 경곽이는 몇 그루의 나무를 골라서 조명을 설치하기로 했다. 조명은 아름다운 정도를 나타내는 값이 정해져 있다. i번째 나무에 설치된 조명의 아름다움은 A_i이다.

경곽이는 너무 가까운 2개의 나무에 모두 조명을 설치하면 나무에게 미치는 영향이 좋지 않다는 사실을 알았다. 구체적으로 j = 1, 2, ... , M에 대해서 나무 L_j, L_j+1, ... R_j 중 2개 이상의 나무에 조명을 설치하지 않기로 했다.

이와 같은 조건으로 조명을 설치하고자 할 때 아름다움의 합의 최댓값을 구하는 프로그램을 작성하시오.

Input

입력은 다음과 같은 조건으로 구성된다.

N M
A_1 A_2 ... A_N
L_1 R_1
L_2 R_2

L_M R_M

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)

[Sub-Task Info]
#1: (10%) N ≦ 16,M ≦ 16
#2: (30%) N ≦ 300,M ≦ 300
#3: (30%) N ≦ 4000,M ≦ 4000
#4: (30%) 추가 제한 조건은 없다.

Output

조명을 설치한 후 아름다움의 합의 최댓값을 출력한다.

IO Example

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

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]