박물관 방문

그로닝거 박물관은 날마다 분위기가 다르다. 조용하고 평화로운 날에는 하루 종일 아름다운 그림, 조각, 그 밖의 작품을 감상할 수 있다. 주말이나 공휴일에는 서두르는 방문객, 오른 입장료, 떠드는 아이들로 북적인다. 불편의 정도도 크게 다르다. 붐비는 날도 학생 할인(studentenkorting) 덕분에 나을 때가 있고, 한산한 날도 지진 위험 때문에 나빠질 수 있다.

박물관은 기간이 정해진 특별 전시도 연다. 지역 축구단 FC 흐로닝언, 마르티니토렌, 에이에르발(지역 특산 음식) 같은 주제의 전시가 그 예다. 전시 기간은 일정하지 않다. 몇 주 동안 이어지는 전시도 있고 하루만 열리는 전시도 있으며, 같은 날 여러 전시가 열리기도 한다.

흐로닝언 사람으로서 모든 전시를 적어도 한 번은 보고 싶다. 뉴스레터를 구독하고 있어서 모든 전시의 시작일과 종료일을 미리 안다. 또 자주 찾는 방문객이라서 날마다 받게 될 불편의 정도를 정확히 알고 있다.

앞으로 열리는 모든 전시를 보면서 불편의 합을 최소로 하려면 어느 날 박물관을 찾아야 할까?

예를 들어 첫 번째 테스트 케이스를 보자. 불편을 최소로 하려면 처음 두 전시는 2일에 보고, 마지막 전시는 4일이나 5일에 보면 된다.

입력은 다음과 같이 주어진다.

• 첫 줄에 두 정수 $n$과 $m$($1\leq n,m\leq 2\cdot10^5$)이 주어진다. $n$은 앞으로 고려할 날의 수이고, $m$은 그 기간에 열리는 전시의 수이다.
• 둘째 줄에 $n$개의 정수 $c$($1\leq c\leq 10^9$)가 주어진다. $c_i$는 $i$일에 방문할 때 받는 불편의 정도이다.
• 이어지는 $m$개의 줄에 전시의 시작일 $s$와 종료일 $e$($1\leq s\leq e\leq n$)가 각각 주어진다. 시작일과 종료일은 모두 포함되므로, $s$일부터 $e$일까지 아무 날에나 전시를 볼 수 있다.

모든 전시를 관람하는 동안 받는 불편의 합의 최솟값을 출력한다.