메뉴 건너뛰기

문제

00c58 조명 2  

시간메모리제출 올바른 답 비율
2초256MB
4
2
50.0%


나의 횟수나의 최근 판정시도 성공 비율
32
66.7%
조명 

코딩펀 집의 정원에는 \(N\)개의 나무가 일렬로 늘어서 있고, 각 나무에는 \(1\) 에서 \(N\)까지의 정수 번호가 매겨져 있다. 단, 인접한 두 나무의 거리는 동일하지 않다.

코딩펀은 나무 몇개를 선택해서 조명을 꾸밀 계획이다. 각 나무에 꾸밀 수 있는 조명에는 '아름다움'이라는 값이 정해져 있으며, 나무 \(i\)에 조명을 꾸밀 경우의 '아름다움'은 \(A_i\)이다.

코딩펀은 인접한 두 나무가 너무 가까운 경우 조명이 너무 눈이 부신다는 사실을 알게 되었다. 즉, \(j = 1,2, ... ,M\)에 대해서, 나무들 사이가 좁은 특정 구간 \(K_j\) 에는 2개 이상의 나무에 조명을 꾸밀 수 없다. 각 구간은 구간의 시작을 나타내는 나무 번호와 구간의 끝을 나타내는 나무 번호로 구성된다. 만약, 구간 \(K_j\)가 2, 4 라고 가정하면, 나무 2에서 나무 4 사이에는 2개 이상의 조명을 꾸밀 수 없다.

이 조건에 따라 코딩펀의 집 정원에 조명으로 꾸밀 수 있는 '아름다움'의  최대값을 구하시오.

입력

첫번째 줄에 나무의 갯수 \(N (1 \leq N \leq 200,000)\)과 조명을 꾸밀 수 없는 구간의 갯수 \(M(1 \leq M \leq 200,000)\)이 공백을 사이에 두고 주어진다.

두번째 줄에 각 나무에 꾸밀 수 있는 조명의 '아름다움' \(A_i(1 \leq A_i \leq 1,000,000,000)\)이 공백을 사이에 두고 주어진다. 단, \(i\)는  \(1 \leq i \leq N\) 이다.

\(M\)개의 줄에 걸쳐, 조명을 꾸밀 수 없는 구간의 시작 번호와 끝 번호가 공백을 사이에 두고 주어진다.

출력

조명의 최대 아름다움을 출력한다.

예시
1입력
4 1
1 2 3 8
2 4
출력
9
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
출처
2019년 일본정보올림피아드 예선 5번 문제
위로