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$.

Difficulty: MEDIUM_HARD

Starter code:

Solutions:
(n, m) = map(int, input().split())
d = {}
sum1 = 0
for _ in range(m):
	(Pi, Ti) = map(int, input().split())
	if Pi not in d:
		d[Pi] = Ti
	else:
		d[Pi] += Ti
	sum1 += d[Pi]
	print(sum1)


from sys import stdin, stdout
input = stdin.readline
r_int = lambda : int(input())
m_int = lambda : map(int, input().split())
l_int = lambda : list(map(int, input()).split())

def main():
	(n_students, n_days) = m_int()
	times = [0] * (n_students + 1)
	tot = 0
	for _ in range(n_days):
		(s, t) = m_int()
		times[s] += t
		tot += times[s]
		print(tot)
main()


(n, m) = map(int, input().split())
a = {}
ans = 0
for i in range(m):
	(p, t) = map(int, input().split())
	if a.get(p) is None:
		a[p] = t
		ans += t
	else:
		a[p] += t
		ans += a[p]
	print(ans)


(n, m) = [int(x) for x in input().split()]
lst = [0] * n
add = 0
for i in range(m):
	(p, t) = [int(x) for x in input().split()]
	lst[p - 1] += t
	add += lst[p - 1]
	print(add)


(n, m) = list(map(int, input().split()))
lst = [0] * n
add = 0
for i in range(m):
	(p, t) = list(map(int, input().split()))
	lst[p - 1] += t
	add += lst[p - 1]
	print(add)


(n, m) = list(map(int, input().split()))
ans = 0
li = {}
for i in range(m):
	(x, y) = list(map(int, input().split()))
	if li.get(x) is None:
		li[x] = y
		ans += y
	else:
		li[x] += y
		ans += li[x]
	print(ans)


(n, m) = map(int, input().split())
a = {}
ans = 0
for i in range(m):
	(p, t) = map(int, input().split())
	if p not in a:
		a[p] = t
		ans += t
	else:
		a[p] += t
		ans += a[p]
	print(ans)


(n, m) = map(int, input().split())
cnt = {}
ans = 0
for i in range(m):
	(a, b) = map(int, input().split())
	if cnt.get(a) == None:
		ans += b
		cnt[a] = b
	else:
		cnt[a] += b
		ans += cnt[a]
	print(ans)


from collections import defaultdict
(n, m) = map(int, input().split())
prev = 0
d = defaultdict(lambda : 0)
for i in range(m):
	(k, v) = map(int, input().split())
	d[k] += v
	prev += d[k]
	print(prev)


(n, m) = map(int, input().split())
ans = 0
dic = {}
for i in range(1, n + 1):
	dic[i] = []
for i in range(m):
	(p, t) = map(int, input().split())
	if len(dic[p]) == 0:
		dic[p].append(t)
		ans = ans + dic[p][-1]
		print(ans)
	else:
		dic[p].append(dic[p][-1] + t)
		ans = ans + dic[p][-1]
		print(ans)


q = str(input())
q = q + ' '
w = ''
e = []
for i in q:
	if i == ' ':
		e.append(int(w))
		w = ''
	else:
		w = w + i
t = {}
a = 0
for i in range(e[1]):
	r = str(input())
	r = r + ' '
	y = ''
	for j in range(len(r)):
		if r[j] == ' ':
			if y not in t:
				t[y] = 0
			t[y] = t[y] + int(r[j + 1:len(r)])
			break
		else:
			y = y + r[j]
	a = a + t[y]
	print(a)


(n, m) = map(int, input().split(' '))
arr = [0 for i in range(n + 1)]
ans = 0
for j in range(m):
	(p, t) = map(int, input().split(' '))
	arr[p] += t
	ans += arr[p]
	print(ans)


(a, b) = map(int, input().split())
x = {}
ans = 0
for i in range(b):
	(p, t) = map(int, input().split())
	try:
		x[p] += t
	except:
		x[p] = t
	ans += x[p]
	print(ans)


a = [int(ele) for ele in input().split()]
(sum2, sum1) = (0, 0)
q = [0 for i in range(a[0] + 1)]
for i in range(0, a[1], 1):
	p = [int(ele) for ele in input().split()]
	q[p[0]] = q[p[0]] + p[1]
	sum1 = sum1 + q[p[0]]
	print(sum1)


def SumOfSubset(a, n):
	k = n
	Sum = 0
	for i in range(n):
		Sum = Sum + a[i] * k
		k -= 1
	return Sum
(N, M) = map(int, input().split(' '))
d = {}
final_ans = 0
for i in range(M):
	(p, t) = map(int, input().split())
	y = 0
	try:
		d[p][0] += t
		d[p][1] += d[p][0]
		final_ans += d[p][0]
	except:
		d[p] = [t, t]
		final_ans += t
	print(final_ans)


(n, m) = map(int, input().split())
d = {}
res = 0
for _ in range(m):
	(p, t) = map(int, input().split())
	if d.get(p) is None:
		d[p] = t
		res += t
	else:
		d[p] += t
		res += d[p]
	print(res)


(M, N) = map(int, input().split())
Army = {}
Final = 0
for T in range(N):
	(k, l) = map(int, input().split())
	Final += l
	if Army.get(k) == None:
		Army[k] = l
	else:
		Final += Army[k]
		Army[k] += l
	print(Final)


(m, n) = map(int, input().split())
(vk, d) = ([], 0)
for i in range(m + 1):
	vk.append([0])
while n:
	(a, b) = map(int, input().split())
	vk[a].append(vk[a][-1] + b)
	print(vk[a][-1] + d)
	d += vk[a][-1]
	n -= 1


(m, n) = map(int, input().split())
a = []
for i in range(m + 1):
	a.append([0])
s = 0
while n:
	(i, j) = map(int, input().split())
	a[i].append(a[i][-1] + j)
	s += a[i][-1]
	print(s)
	n -= 1


(n, m) = map(int, input().split())
dp = [0] * (n + 1)
count = 0
for _ in range(m):
	(P, T) = map(int, input().split())
	count = count + dp[P] + T
	print(count)
	dp[P] += T


(N, M) = map(int, input().split())
answ = 0
t = [0] * N
for i in range(M):
	(a, b) = map(int, input().split())
	t[a - 1] += b
	answ += t[a - 1]
	print(answ)


from collections import defaultdict
(n, m) = map(int, input().split())
mx = 0
ans = 0
cnt = defaultdict(int)
for _ in range(m):
	(x, y) = map(int, input().split())
	cnt[x] += y
	if cnt[x] > mx:
		ans += cnt[x]
		mx = cnt[x]
	else:
		ans += cnt[x]
	print(ans)


(n, m) = map(int, input().split())
dic = [0] * (n + 1)
res = 0
while m:
	(P, T) = map(int, input().split())
	dic[P] += T
	res += dic[P]
	print(res)
	m -= 1


(N, M) = map(int, input().split())
A = [0 for i in range(N + 1)]
x = 0
for i in range(M):
	(P, T) = map(int, input().split())
	A[P] += T
	x += A[P]
	print(x)


(n, m) = input().split()
n = int(n)
m = int(m)
d = {}
for i in range(1, n + 1):
	d[i] = 0
s = 0
while m:
	(p, t) = input().split()
	p = int(p)
	t = int(t)
	d[p] += t
	s += d[p]
	print(s)
	m -= 1


(n, m) = map(int, input().split())
rr = []
hash_map = {}
ans = 0
for i in range(m):
	(a, b) = map(int, input().split())
	if a in hash_map:
		ans += hash_map[a] + b
		hash_map[a] = hash_map[a] + b
	else:
		ans += b
		hash_map[a] = b
	rr.append(ans)
for i in rr:
	print(i)


def solve(army, a, b):
	army[a - 1] += b
	return army[a - 1]
(n, m) = map(int, input().split())
(army, ans) = ([0 for _ in range(n)], 0)
for _ in range(m):
	ans += solve(army, *map(int, input().split()))
	print(ans)


(n, m) = map(int, input().split())
d = {}
s = 0
for ki in range(m):
	(a, b) = map(int, input().split())
	if a not in d:
		d[a] = 0
	d[a] += b
	s += d[a]
	print(s)


(n, m) = map(int, input().split())
d = {}
tot = 0
for i in range(m):
	(pi, ti) = map(int, input().split())
	if pi not in d:
		tot += ti
		d[pi] = ti
		print(tot)
	else:
		d[pi] += ti
		print(d[pi] + tot)
		tot += d[pi]


(n, m) = map(int, input().split())
d = {}
ans = 0
for _ in range(m):
	(p, t) = map(int, input().split())
	if p not in d:
		d[p] = t
	else:
		d[p] = d[p] + t
	ans += d[p]
	print(ans)


(n, m) = map(int, input().split())
s = 0
d = {}
for i in range(m):
	(p, t) = map(int, input().split())
	if p not in d:
		d[p] = t
	else:
		d[p] += t
	s += d[p]
	print(s)


(n1, t1) = map(int, input().split())
ayush = [0] * (n1 + 1)
sum = 0
for _ in range(t1):
	(i, v) = map(int, input().split())
	ayush[i] += v
	sum += ayush[i]
	print(sum)


(n, m) = list(map(int, input().split()))
C = [0 for _ in range(n + 1)]
res = 0
for _ in range(m):
	(p, t) = list(map(int, input().split()))
	C[p] += t
	res += C[p]
	print(res)


(n, m) = map(int, input().split())
ans = 0
li = {}
for i in range(m):
	(pi, ti) = map(int, input().split())
	if pi in li.keys():
		li[pi] = li[pi] + ti
		ans = ans + li[pi]
	else:
		li[pi] = ti
		ans = ans + li[pi]
	print(ans)


(n, m) = map(int, input().split())
l = [0] * n
sum = 0
for i in range(m):
	(p, t) = map(int, input().split())
	if l[p - 1] == 0:
		l[p - 1] += t
		sum += t
		print(sum)
	else:
		l[p - 1] += t
		sum += l[p - 1]
		print(sum)


(a, b) = map(int, input().split())
d = {}
c = 0
for i in range(b):
	(x, y) = map(int, input().split())
	if x in d:
		d[x] += y
	else:
		d[x] = y
	c = c + d[x]
	print(c)


(a, b) = map(int, input().split())
dic = {}
res = 0
for _ in range(b):
	(p, t) = map(int, input().split())
	if p not in dic.keys():
		dic[p] = 0
	dic[p] += t
	res += dic[p]
	print(res)


(n, m) = map(int, input().split())
(p, t) = ([], [])
for _ in range(m):
	(a, b) = map(int, input().split())
	p.append(a)
	t.append(b)
d = {}
for i in range(m):
	if p[i] in d:
		d[p[i]] += t[i]
	else:
		d[p[i]] = t[i]
	if i == 0:
		t[i] = t[i]
	else:
		t[i] = t[i - 1] + d[p[i]]
print(*t, sep='\n')


from collections import defaultdict
(n, m) = map(int, input().split(' '))
res = 0
tasks = defaultdict(lambda : 0)
for _ in range(m):
	(p, t) = map(int, input().split(' '))
	res += tasks[p] + t
	print(res)
	tasks[p] += t


(n, T) = map(int, input().split())
waiting = [0] * n
ans = 0
for _ in range(T):
	(p, t) = map(int, input().split())
	ans = ans + t + waiting[p - 1]
	print(ans)
	waiting[p - 1] += t


def main():
	(n, m) = map(int, input().split())
	task = {}
	curr = 0
	for i in range(m):
		(u, v) = map(int, input().split())
		if u not in task:
			task[u] = v
			curr += v
		else:
			task[u] += v
			curr += task[u]
		print(curr)
	return
main()


try:
	obj = {}
	(n, m) = map(int, input().split())
	ans = 0
	for i in range(m):
		(a, b) = map(int, input().split())
		if a in obj.keys():
			obj[a] += b
			ans += obj[a]
			print(ans)
		else:
			obj[a] = b
			ans += b
			print(ans)
except:
	pass


(n, m) = map(int, input().split())
T = [0] * int(1000000.0 + 1)
ans = 0
for _ in range(m):
	(x, y) = map(int, input().split())
	T[x] += y
	ans += T[x]
	print(ans)


(n, m) = map(int, input().split())
s = 0
d = {}
for i in range(m):
	(k, l) = map(int, input().split())
	if k not in d:
		d[k] = l
		s += l
	else:
		d[k] += l
		s += d[k]
	print(s)


(N, M) = [int(i) for i in input().split()]
list1 = []
for i in range(N):
	list1.append(0)
train = 0
for j in range(M):
	(a, b) = [int(x) for x in input().split()]
	for j in range(20):
		j = 9
	list1[a - 1] = list1[a - 1] + b
	for j in range(20):
		j = 9
	train = train + list1[a - 1]
	for j in range(20):
		j = 9
	print(train)


(m, t) = map(int, input().split())
di = {}
s = 0
for i in range(0, t):
	(a, b) = map(int, input().split())
	if a not in di:
		di[a] = b
		s += b
		print(s)
	else:
		di[a] += b
		s += di[a]
		print(s)


(n, m) = [int(x) for x in input().split(' ')]
A = []
for i in range(m):
	a = [int(x) for x in input().split(' ')]
	A.append(a)
d = dict()
ans = 0
for i in range(m):
	v = A[i][0]
	t = A[i][1]
	if d.get(v, -1) == -1:
		ans += t
		d[v] = t
		print(ans)
	else:
		d[v] = d.get(v) + t
		ans += d.get(v)
		print(ans)


def Answer_here():
	(n, m) = map(int, input().split())
	halfy = 1000000 + 1
	ttt = [0] * halfy
	fully = ttt
	soln = 0
	for i in range(m):
		(a, b) = map(int, input().split())
		fully[a] = fully[a] + b
		nnn = fully[a]
		soln = soln + nnn
		print(soln)
Answer_here()


for _ in range(1):
	(n, m) = map(int, input().split())
	total = [0] * (int(1000000.0) + 1)
	ans = 0
	for i in range(m):
		(a, b) = map(int, input().split())
		total[a] += b
		ans += total[a]
		print(ans)


(n, m) = map(int, input().split())
mi = [0] * (n + 1)
tim = 0
for i in range(m):
	(a, b) = map(int, input().split())
	tim += b + mi[a]
	mi[a] += b
	print(tim)


(n, m) = map(int, input().split())
ans = 0
d = {}
while m:
	(a, b) = map(int, input().split())
	if a not in d:
		d[a] = b
	else:
		d[a] += b
	ans += d[a]
	print(ans)
	m -= 1


(a, b) = map(int, input().split())
answer = 0
a = {}
for i in range(b):
	(p, q) = map(int, input().split())
	t = 0
	if a.get(p):
		t = a[p]
	answer += q + t
	print(answer)
	if a.get(p):
		a[p] += q
	else:
		a[p] = q


(n, m) = map(int, input().split())
d = {}
t = 0
for i in range(m):
	(a, b) = map(int, input().split())
	if a not in d:
		d[a] = b
	else:
		d[a] = d.get(a) + b
	t += d[a]
	print(t)


(a, b) = [int(x) for x in input().split()]
x = {}
a = 0
for _ in range(b):
	(n, m) = [int(x) for x in input().split()]
	if n not in x:
		x[n] = m
		a += m
	else:
		x[n] = x[n] + m
		a += x[n]
	print(a)


(n, m) = map(int, input().split())
d = {}
s = 0
for _ in range(m):
	(p, t) = map(int, input().split())
	try:
		d[p] += t
		s += d[p]
	except:
		d[p] = t
		s += t
	print(s)


(s, n) = map(int, input().split())
l = []
c = 0
r = []
d = {}
for i in range(n):
	(a, b) = map(int, input().split())
	if a not in d:
		d[a] = b
	else:
		d[a] += b
	r.append(d[a] + c)
	c = d[a] + c
for i in r:
	print(i)


(n, m) = map(int, input().split())
sol = 0
arr = {}
for _ in range(m):
	(p, t) = map(int, input().split())
	sol += arr.get(p, 0) + t
	print(sol)
	arr[p] = arr.get(p, 0) + t


(n, m) = [int(x) for x in input().rstrip().split()]
ans = 0
l = [0] * 99999999
for i in range(0, m):
	(a, b) = [int(x) for x in input().rstrip().split()]
	l[a] += b
	ans += l[a]
	print(ans)


(m, n) = map(int, input().split())
l = []
for _ in range(n):
	a = list(map(int, input().split()))
	l.append(a)
w = {}
s = 0
for i in l:
	if i[0] not in w:
		w[i[0]] = i[1]
		s += i[1]
		print(s)
	else:
		w[i[0]] += i[1]
		s += w[i[0]]
		print(s)


(n, m) = map(int, input().split())
d1 = {}
net1 = 0
for i in range(m):
	(me, t) = map(int, input().split())
	d1.setdefault(me, 0)
	d1[me] += t
	net1 += d1[me]
	print(net1)


(a, b) = map(int, input().split())
d = {}
for i in range(1, a + 1):
	d[i] = d.get(i, 0)
c = 0
for i in range(b):
	(p, t) = map(int, input().split())
	d[p] += t
	c += d[p]
	print(c)


def solve():
	(n, m) = map(int, input().split())
	total = [0] * (int(1000000.0) + 1)
	ans = 0
	for i in range(m):
		(a, b) = map(int, input().split())
		total[a] = total[a] + b
		ans = ans + total[a]
		print(ans)
T = 1
while T:
	solve()
	T = T - 1


(n, m) = [int(x) for x in input().split()]
l = [0] * (10 ** 6 + 1)
ans = 0
for i in range(m):
	(a, b) = [int(x) for x in input().split()]
	l[a] += b
	ans += l[a]
	print(ans)


import collections
(n, m) = map(int, input().split())
a = {}
t1 = []
sum = 0
for i in range(m):
	(p, t) = map(int, input().split())
	sum += t
	if p not in a:
		a[p] = t
	else:
		sum += a[p]
		a[p] += t
	t1.append(sum)
print(*t1, sep='\n')


vals = input().split()
N = int(vals[0])
M = int(vals[1])
u_m = {}
sum = 0
for i in range(M):
	vals = input().split()
	P = int(vals[0])
	T = int(vals[1])
	if P not in u_m:
		u_m[P] = T
	else:
		u_m[P] += T
	sum += u_m[P]
	print(sum)


from sys import stdin
input = stdin.readline
from collections import defaultdict
import heapq

def solve(N, M, tasks):
	participants = defaultdict(lambda : 0)
	ans = 0
	for task in tasks:
		participants[task[0]] += task[1]
		ans += participants[task[0]]
		print(ans)
	return 0
(n, k) = map(int, input().split())
t = []
for i in range(k):
	a = tuple(map(int, input().split()))
	t.append(a)
solve(n, k, t)


(a, b) = map(int, input().split())
d = {}
t = 0
for _ in range(b):
	(x, y) = map(int, input().split())
	if x not in d:
		d[x] = y
		t += y
		print(t)
	else:
		d[x] += y
		t += d[x]
		print(t)


(n, m) = [int(x) for x in input().split()]
lst = []
for i in range(n):
	lst.append(0)
s = 0
for i in range(m):
	(a, b) = [int(x) for x in input().split()]
	lst[a - 1] = lst[a - 1] + b
	s += lst[a - 1]
	print(s)


(n, m) = map(int, input().split())
r = {}
res = 0
for i in range(m):
	(p, t) = map(int, input().split())
	if p not in r:
		r[p] = t
	else:
		r[p] += t
	res += r[p]
	print(res)


(a, b) = map(int, input().split())
dic = {}
z = 0
for i in range(b):
	(y, x) = map(int, input().split())
	if y not in dic:
		dic[y] = x
		z += x
		print(z)
	else:
		dic[y] += x
		z += dic[y]
		print(z)


(n, m) = map(int, input().split())
ans = 0
mp = {}
for _ in range(m):
	(p, t) = map(int, input().split())
	ans += mp.get(p, 0) + t
	print(ans)
	mp[p] = mp.get(p, 0) + t


(n, m) = map(int, input().split())
array = [0] * 1000001
s = 0
for i in range(m):
	(a, b) = map(int, input().split())
	array[a - 1] += b
	s += array[a - 1]
	print(s)


(h, j) = map(int, input().split())
dic = {}
u = 0
for i in range(j):
	(t, r) = map(int, input().split())
	if t not in dic:
		dic[t] = r
		u += r
		print(u)
	else:
		dic[t] += r
		u += dic[t]
		print(u)


(n, m) = map(int, input().strip().split())
summ = [0] * (int(1000000.0) + 1)
res = 0
for i in range(m - m + m - 23 + 23):
	(a, b) = map(int, input().strip().split())
	summ[a] += b
	res += summ[a]
	print(res)


(x, y) = map(int, input().split())
time = 0
l = {}
for i in range(y):
	(n, t) = map(int, input().split())
	if n not in l.keys():
		time += t
		l[n] = t
	else:
		l[n] += t
		time += l[n]
	print(time)


(n, m) = map(int, input().split())
g = {i: 0 for i in range(1, n + 1)}
count = 0
for _ in range(m):
	(x, y) = map(int, input().split())
	g[x] += y
	count += g[x]
	print(count)


(n, m) = map(int, input().split())
s = 0
dic = {}
for i in range(m):
	(a, b) = map(int, input().split())
	if a not in dic:
		dic[a] = b
		s += b
	else:
		dic[a] += b
		s += dic[a]
	print(s)