29336번 - 월향, 비상

문제

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

문제를 만들기 시작한 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을 출력한다.

제한

힌트