코딩펀 집의 정원에는 \(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\)개의 줄에 걸쳐, 조명을 꾸밀 수 없는 구간의 시작 번호와 끝 번호가 공백을 사이에 두고 주어진다.
조명의 최대 아름다움을 출력한다.