Dumbledore's Army consists of N members. Alice Potter is planning to hold M Dumbledore's Army sessions, where the members will perform training tasks to improve their skills in Defense Against the Dark Arts.

Initially, each member of the Army has no tasks. Before the i-th training session, Alice gives the P_{i}-th participant a task that he can complete in T_{i} seconds. And each subsequent session Alice will add more and more difficult tasks, i.e. T_{i} ≤ T_{i+1}.

Let's assume that by the i-th session, the j-th participant has accumulated C_{j} tasks. Alice knows that sometimes there is not enough time to complete all the tasks in a single session, so instead of forcing them to complete all $C_{1}+C_{2}+\ldots+C_{N}$ tasks, she can allow them to complete only a certain number k of them. In this case, each participant can choose a subset of their tasks (in total, they have to choose k tasks) and perform only those tasks. Each participant performs his tasks sequentially and spends time equal to the sum of the times of his tasks. However, different participants can perform tasks in parallel, so the total time of the session is equal to the maximum of the times of each participant. We denote the minimum possible value of this time by ans_{i, k}.

In order to optimally train participants, for each session i Alice needs to know the value of $ans_{i, 1} + ans_{i, 2} + \ldots + ans_{i, i}.$ Help Alice — calculate these sums for her.

------ Input Format ------

• The first line contains two integers N and M — the number of members of Dumbledore's Army and the number of classes.

• The i-th of the next M lines contains two integers P_{i} and T_{i} — the participant who will receive the next task and the amount of time it will take to complete it.

------ Output Format ------

Print M integers. The i-th of them should be equal to $ans_{i, 1} + ans_{i, 2} + \ldots + ans_{i, i}$.

------ Constraints ------

$1 ≤N, M ≤10^{6}$
$1 ≤P_{i} ≤N$, $1 ≤T_{i} ≤10^{6}$
$T_{1} ≤T_{2} ≤\ldots ≤T_{M}$

------ subtasks ------

Subtask 1 (10 points): $1 ≤ M ≤ 10$
Subtask 2 (20 points): The sum of $N$ across all test cases won't exceed $20$.
Subtask 3 (70 points): No further constraints.

----- Sample Input 1 ------
5 12
5 1
3 2
5 2
1 2
4 3
4 3
4 3
5 3
1 5
3 5
1 8
2 10

----- Sample Output 1 ------
1
3
6
8
11
17
26
32
39
46
61
71

----- explanation 1 ------
Consider the third session in the example. The fifth participant has tasks with $T=1$ and $T=2$, and the third participant has a single task with $T=2$. It takes $1$ unit of time to complete one task (only the fifth participant will complete the task with $T=1$), $2$ unit of time to complete two tasks, and $3$ unit of time to complete all three tasks. Therefore, the third number in the answer is $1+2+3=6$.

见题面

见题面