월향, 비상

시간 제한1초메모리 제한1024 MB

요약

운영진 N명의 역량이 매일 1씩 늘고 각자 한 번만 문제를 만들거나 기존 문제의 퀄리티를 높일 수 있을 때, M개의 누적 퀄리티 조건을 모두 만족하면서 마지막 조건 날까지 얻을 수 있는 최대 퀄리티 합을 구한다.

난이도: 보통10점 중 7점
유형: 그리디, 정렬, 누적 합, 이분 탐색
정답자: 아직 제출이 없습니다

문제

월간 향유회(이하 월향)의 운영진들은 고민에 빠졌다. 당장 이번 달 대회에 출제할 문제가 부족하기 때문이었다. 위기의 대회를 구할 마지막 희망, 박신욱은 운영진들이 힘을 합쳐 문제를 만들 것을 제안하였다.

문제를 만들기 시작한 $0$ 일 째에 운영진 $N$ 명의 역량은 각각 $A\_i$ 와 같다. 월향의 운영진들은 성장하는 인재이므로 하루가 지날 때마다 역량이 $1$ 씩 늘어난다. 운영진들은 본인의 역량에 준하는 퀄리티의 문제를 만들거나, 본인의 역량만큼 기존 문제 중 하나의 퀄리티를 높일 수 있다. 문제를 만들거나 기존 문제의 퀄리티를 높이는 데에는 시간이 걸리지 않는다. 단, 한 번 대회에 기여한 운영진은 힘들어서 더 이상 대회에 기여할 수 없다.

대회가 원활하게 준비되기 위해서는 진행 상황이 점차 진척되어야 한다. 이는 $M$ 개의 조건으로 표현할 수 있다.

$T\_i$ 일까지 만들어진 문제들의 퀄리티의 합이 $Q\_i$ 이상이어야 한다.

월향의 운영진들이 조건을 모두 만족하면서 최적으로 문제를 만들었을 때, 마지막 조건이 있는 날까지 만들어진 문제들의 최대 퀄리티 합을 구하여라.

입력

첫째 줄에 운영진의 수 $N$ 과 조건의 수 $M$ 이 공백으로 구분되어 주어진다. $(1 \leq N, M \leq 200\ 000)$

둘째 줄에 각 운영진의 역량을 뜻하는 $N$ 개의 정수 $A\_1, A\_2, \cdots, A\_N$ 이 공백으로 구분되어 주어진다. $(1 \leq A\_i \leq 10^9)$

셋째 줄부터 $M$ 개의 줄에 각 조건을 나타내는 두 정수 $T\_i$ , $Q\_i$ 가 공백으로 구분되어 주어진다. $(1 \leq T\_i, Q\_i \leq 10^9)$

배열 $T$ 와 $Q$ 는 각각 오름차순으로 주어진다.

출력

모든 조건을 만족하도록 문제를 만들었을 때, 마지막 조건의 날까지 만들어진 문제들의 퀄리티의 합으로 가능한 최댓값을 출력한다. 만약 문제를 어떻게 만들어도 모든 조건을 만족할 수 없다면 대신 -1을 출력한다.

예제2

예제 1
입력
```
4 3
4 3 6 1
1 2
3 8
4 10
```
예상 출력
```
26
```
예제 2
입력
```
2 1
2 5
1 10
```
예상 출력
```
-1
```