\(N\)개의 광맥이 있다. 0일 차에 \(i\)번째 광맥에서 채굴할 수 있는 GOLD의 양은 \(A_i\)이다.

탐사가 계속되면서 각 광맥에서 채굴할 수 있는 GOLD의 양은 하루마다 1씩 증가한다. 따라서 \(t\)일 차에 \(i\)번째 광맥을 채굴하면 \(A_i+t\)만큼의 GOLD를 얻는다. 광맥을 채굴하는 데에는 시간이 걸리지 않으며, 각 광맥은 한 번만 채굴할 수 있다.

채굴 계획에는 다음과 같은 \(M\)개의 조건이 있다.

• \(T_i\)일까지 채굴한 GOLD의 총합이 \(Q_i\) 이상이어야 한다.

모든 조건을 만족하면서 채굴했을 때, 마지막 조건이 있는 날까지 얻을 수 있는 GOLD 총합의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 광맥의 수 \(N\)과 조건의 수 \(M\)이 공백으로 구분되어 주어진다.

둘째 줄에 각 광맥에서 0일 차에 채굴할 수 있는 GOLD의 양 \(A_1, A_2, \dots, A_N\)이 공백으로 구분되어 주어진다.

셋째 줄부터 \(M\)개의 줄에 걸쳐 각 조건을 나타내는 두 정수 \(T_i\)와 \(Q_i\)가 공백으로 구분되어 주어진다.

출력

모든 조건을 만족할 수 있다면, 마지막 조건이 있는 날까지 얻을 수 있는 GOLD 총합의 최댓값을 출력한다.

모든 조건을 만족할 수 없다면 -1을 출력한다.

제한 사항

• \(1 \le N, M \le 200,000\)
• \(1 \le A_i \le 1,000,000,000\)
• \(1 \le T_i, Q_i \le 1,000,000,000\)
• \(T_1 \le T_2 \le \dots \le T_M\)
• \(Q_1 \le Q_2 \le \dots \le Q_M\)

예제 입력 1

4 3
2 5 1 4
1 6
3 12
5 20

예제 출력 1

26

예제 설명 1

1일 차에 두 번째 광맥을 채굴하면 \(5+1=6\) GOLD를 얻어 첫 번째 조건을 만족한다.

3일 차에 네 번째 광맥을 채굴하면 \(4+3=7\) GOLD를 추가로 얻는다. 지금까지 얻은 GOLD는 \(13\)이므로 두 번째 조건도 만족한다.

5일 차에 남은 두 광맥을 모두 채굴하면 각각 \(2+5=7\), \(1+5=6\) GOLD를 얻는다. 따라서 마지막 조건을 만족하며, 얻은 GOLD의 총합은 \(26\)이다.

예제 입력 2

2 1
1 2
1 100

예제 출력 2

-1