구간 합 최대

승현이는 음이 아닌 정수 $N$개로 이루어진 배열을 가지고 논다. 이 배열에는 특별한 조건이 $M$개 붙어 있다. $i$번째 조건은 길이가 $L_i$인 연속한 구간을 어떻게 잡아도 그 구간의 합이 $S_i$를 넘지 않는다는 뜻이다.

승현이는 조건을 모두 만족하는 배열을 전부 만들어 놓고, $1$ 이상 $N$ 이하의 모든 정수 $K$마다 각 배열에서 길이가 $K$인 연속한 구간의 합을 모두 구한 뒤 그중 가장 큰 값을 찾았다. 계산에 자신이 없어 결과를 확신하지 못한다고 하니 대신 구해 주자.

정리하면 $K$마다 조건을 모두 만족하는 배열 하나와 그 배열에서 길이가 $K$인 연속한 구간 하나를 함께 골랐을 때 나올 수 있는 구간 합의 최댓값을 구하는 문제다.

첫째 줄에 배열을 이루는 정수의 개수 $N$($1 \le N \le 200\,000$)과 특별한 조건의 개수 $M$($1 \le M \le 200$)이 주어진다.

둘째 줄부터 $M$개의 줄에 조건을 나타내는 두 정수 $L_i$와 $S_i$가 주어진다. ($1 \le i \le M$, $1 \le L_i \le N$, $1 \le S_i \le 10^9$)

길이가 같은 조건이 여러 번 주어지기도 한다.

$N$개의 줄을 출력한다. $K$번째 줄에는 조건을 모두 만족하는 배열에서 길이가 $K$인 연속한 구간이 가질 수 있는 구간 합의 최댓값을 출력한다.

$N = 5$이고 조건이 길이 $2$에 합 $5$, 길이 $3$에 합 $7$인 경우를 보자. 배열이 [1, 4, 1, 0, 5]이면 길이가 1인 구간 중 합이 5인 것이 있고, 길이가 2인 구간 중 합이 5인 것이 있고, 길이가 4인 구간 중 합이 10인 것이 있다. 배열이 [3, 2, 2, 1, 4]이면 길이가 3인 구간 중 합이 7인 것이 있고, 길이가 5인 구간 중 합이 12인 것이 있다.