데이트 약속

커플이 된 록금이는 $N$일간의 데이트 약속을 잡기로 했다!

록금이 커플은 연속으로 데이트할수록 하루에 얻을 수 있는 애정이 점점 늘어난다. 구체적으로 연속 $1$일차에는 $1$, 연속 $2$일차에는 $2$, $\cdots$, 연속 $i$일차에는 $i$만큼의 애정을 얻을 수 있다. 즉 $3$일 연속으로 데이트한다면 $1 + 2 + 3 = 6$의 애정을 얻는다.

솔로였던 쿠민이는 커플이 된 록금이가 보기 싫었다. 그래서 쿠민이는 $X_1, X_2, \cdots, X_M$일에 저주를 걸어, 록금이 커플이 $X_j$일차에 데이트한다면 록금이 커플의 애정이 $Y_j$만큼 깎이도록 만들었다. 저주 걸린 날에 데이트하더라도 연속 $i$일차에 $i$만큼의 애정을 얻을 수 있다는 사실에는 변함이 없다. 안타깝게도, 저주로 인해 특정 날짜까지의 누적 애정 총합이 음수가 될 수 있다.

쿠민이의 괘씸한 계획을 알게 된 록금이는 애정을 최대로 얻기 위한 데이트 약속을 다시 잡기로 했다. 록금이를 도와 $N$일간의 데이트를 끝마쳤을 때, 록금이 커플이 최대로 얻을 수 있는 애정의 총합을 구해보자.

첫째 줄에 데이트 일정을 짤 날짜의 수 $N$, 저주에 걸린 날짜의 수 $M$이 공백으로 구분되어 주어진다.

둘째 줄부터 $M$개의 줄에 걸쳐, $j+1$번째 줄에 저주에 걸린 날짜 $X_j$, 깎이는 애정량 $Y_j$가 공백으로 구분되어 주어진다.

$(X_j,\ Y_j)$는 $X_j$에 대해 오름차순으로 주어지며, 모든 $X_j$는 서로 다르다.

록금이 커플이 최대로 얻을 수 있는 애정의 총합을 출력한다.

• $1 \leq N \leq 400\,000$
• $0 \leq M \leq \min(4\,000, N)$
• $1 \leq X_j \leq N$ $(1 \leq j \leq M)$
• $1 \leq Y_j \leq 10^9$ $(1 \leq j \leq M)$

입력으로 주어지는 수는 모두 정수이다.