조명 |
---|
코딩펀 집의 정원에는 \(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번 문제 |