Largest window sum

Seunghyun plays with an array of $N$ non-negative integers. The array carries $M$ special conditions. Condition $i$ says that every contiguous window of length $L_i$ has a sum of at most $S_i$.

Seunghyun wrote down every array that satisfies all of the conditions. For each integer $K$ between $1$ and $N$ he took every contiguous window of length $K$ in each of those arrays, computed its sum, and kept the largest value. He is not confident about his arithmetic, so compute the answers for him.

In other words, for each $K$ report the largest window sum you can reach by choosing an array that satisfies every condition together with a contiguous window of length $K$ inside it.

The first line contains the number of integers in the array $N$ ($1 \le N \le 200\,000$) and the number of special conditions $M$ ($1 \le M \le 200$).

Each of the next $M$ lines contains two integers $L_i$ and $S_i$ describing one condition ($1 \le i \le M$, $1 \le L_i \le N$, $1 \le S_i \le 10^9$).

Several conditions may share the same length.

Print $N$ lines. Line $K$ holds the largest sum a contiguous window of length $K$ can have in an array that satisfies every condition.

Take $N = 5$ with two conditions: length $2$ with bound $5$, and length $3$ with bound $7$. For the array [1, 4, 1, 0, 5] there is a window of length 1 whose sum is 5, a window of length 2 whose sum is 5, and a window of length 4 whose sum is 10. For the array [3, 2, 2, 1, 4] there is a window of length 3 whose sum is 7, and a window of length 5 whose sum is 12.