There are n servers in a laboratory, each of them can perform tasks. Each server has a unique id — integer from 1 to n.

It is known that during the day q tasks will come, the i-th of them is characterized with three integers: t_{i} — the moment in seconds in which the task will come, k_{i} — the number of servers needed to perform it, and d_{i} — the time needed to perform this task in seconds. All t_{i} are distinct.

To perform the i-th task you need k_{i} servers which are unoccupied in the second t_{i}. After the servers begin to perform the task, each of them will be busy over the next d_{i} seconds. Thus, they will be busy in seconds t_{i}, t_{i} + 1, ..., t_{i} + d_{i} - 1. For performing the task, k_{i} servers with the smallest ids will be chosen from all the unoccupied servers. If in the second t_{i} there are not enough unoccupied servers, the task is ignored.

Write the program that determines which tasks will be performed and which will be ignored.


-----Input-----

The first line contains two positive integers n and q (1 ≤ n ≤ 100, 1 ≤ q ≤ 10^5) — the number of servers and the number of tasks. 

Next q lines contains three integers each, the i-th line contains integers t_{i}, k_{i} and d_{i} (1 ≤ t_{i} ≤ 10^6, 1 ≤ k_{i} ≤ n, 1 ≤ d_{i} ≤ 1000) — the moment in seconds in which the i-th task will come, the number of servers needed to perform it, and the time needed to perform this task in seconds. The tasks are given in a chronological order and they will come in distinct seconds. 


-----Output-----

Print q lines. If the i-th task will be performed by the servers, print in the i-th line the sum of servers' ids on which this task will be performed. Otherwise, print -1.


-----Examples-----
Input
4 3
1 3 2
2 2 1
3 4 3

Output
6
-1
10

Input
3 2
3 2 3
5 1 2

Output
3
3

Input
8 6
1 3 20
4 2 1
6 5 5
10 1 1
15 3 6
21 8 8

Output
6
9
30
-1
15
36



-----Note-----

In the first example in the second 1 the first task will come, it will be performed on the servers with ids 1, 2 and 3 (the sum of the ids equals 6) during two seconds. In the second 2 the second task will come, it will be ignored, because only the server 4 will be unoccupied at that second. In the second 3 the third task will come. By this time, servers with the ids 1, 2 and 3 will be unoccupied again, so the third task will be done on all the servers with the ids 1, 2, 3 and 4 (the sum of the ids is 10).

In the second example in the second 3 the first task will come, it will be performed on the servers with ids 1 and 2 (the sum of the ids is 3) during three seconds. In the second 5 the second task will come, it will be performed on the server 3, because the first two servers will be busy performing the first task.

Difficulty: EASY
Tags: Implementation

Starter code:

Solutions:
import sys
input = sys.stdin.readline
(n, q) = list(map(int, input().split()))
servers = [0 for i in range(n)]
for i in range(q):
	(time, serv, leng) = list(map(int, input().split()))
	pos = []
	for j in range(n):
		if servers[j] <= time:
			pos.append(j)
	if len(pos) < serv:
		print(-1)
		continue
	pos = pos[:serv]
	for j in pos:
		servers[j] = time + leng
	print(sum(pos) + len(pos))


import math
import sys

def solve(n, q):
	servers = [0] * n
	res = [None] * q
	for (j, line) in enumerate(sys.stdin):
		(t, k, d) = map(int, line.split())
		(S, m) = (k, k)
		logs = servers[:]
		for (i, s) in enumerate(servers):
			if s <= t:
				servers[i] = t + d
				S += i
				m -= 1
			if m == 0:
				res[j] = S
				break
		else:
			res[j] = -1
			servers = logs[:]
	return res
(n, q) = map(int, input().split())
print('\n'.join(map(str, solve(n, q))))


for t in range(1):
	(n, q) = map(int, input().split())
	time = [0] * n
	for i in range(q):
		(t, k, d) = map(int, input().split())
		count = 0
		pos = 0
		for j in range(n):
			if time[j] <= t:
				pos += j + 1
				count += 1
			if count == k:
				break
		if count < k:
			print(-1)
			continue
		changed = 0
		for j in range(n):
			if time[j] <= t:
				time[j] = t + d
				changed += 1
			if changed == count:
				break
		print(pos)


(n, q) = list(map(int, input().split()))
qs = []
ans = [0] * q
used = [0] * n
for _ in range(q):
	(t, k, d) = list(map(int, input().split()))
	less = min(sum((used[i] <= t for i in range(n))), k)
	if less >= k:
		for i in range(n):
			if less == 0:
				break
			if used[i] <= t:
				used[i] = t + d
				ans[_] += i + 1
				less -= 1
	else:
		ans[_] = -1
print('\n'.join(map(str, ans)))


from collections import defaultdict
(n, q) = map(int, input().split())
S = [0] * (n + 1)
S[0] = 1
s = n
L = defaultdict(list)
pre = -1
for i in range(q):
	(t, k, d) = map(int, input().split())
	for j in range(pre, t):
		for l1 in L[j]:
			for l2 in l1:
				S[l2] = 0
				s += 1
	if s >= k:
		tmp = []
		for j in range(1, n + 1):
			if S[j] == 0:
				S[j] = 1
				tmp.append(j)
				if len(tmp) == k:
					break
		s -= k
		L[t + d - 1].append(tmp)
		print(sum(tmp))
		pre = t
	else:
		print(-1)
		pre = t


import heapq as pq
from sys import stdin, stdout
(n, q) = map(int, stdin.readline().split())
server = [i for i in range(1, n + 1)]
running = []
is_chg = False
for x in stdin.readlines():
	(t, k, d) = map(int, x.split())
	while running:
		if t >= running[0][0]:
			server += pq.heappop(running)[1]
			is_chg = True
		else:
			break
	if is_chg:
		server = sorted(server)
		is_chg = False
	if len(server) < k:
		print(-1)
		continue
	else:
		print(sum(server[:k]))
		if d != 1:
			pq.heappush(running, (t + d, server[:k].copy()))
			server = server[k:]


(n, q) = map(int, input().split())
a = [0] * n
for _ in range(q):
	(t, k, d) = map(int, input().split())
	c = 0
	test = 0
	val = []
	for i in range(n):
		if a[i] <= t:
			val.append(i)
			c += i + 1
			k -= 1
		if k == 0:
			test = 1
			break
	if test:
		for i in val:
			a[i] = t + d
		print(c)
	else:
		print(-1)


import sys
try:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
except:
	pass
input = sys.stdin.readline
(n, q) = map(int, input().split())
server = [-1] * n
for _ in range(q):
	(t, k, d) = map(int, input().split())
	cnt = 0
	for i in range(n):
		if t >= server[i]:
			server[i] = -1
		if server[i] == -1:
			cnt += 1
	if k <= cnt:
		ans = 0
		for i in range(n):
			if server[i] == -1:
				server[i] = t + d
				ans += i + 1
				k -= 1
			if not k:
				break
		print(ans)
	else:
		print(-1)


(n, q) = map(int, input().split())
l = [[i, 0] for i in range(1, n + 1)]
for i in range(q):
	(s, k, t) = map(int, input().split())
	old = []
	kk = 0
	for i in range(n):
		el = l[i]
		if el[1] <= s:
			old.append(i)
			kk += 1
		if kk == k:
			break
	if kk == k:
		top = 0
		for ind in old:
			l[ind][1] = s + t
			top += l[ind][0]
		print(top)
	else:
		print(-1)


(n, q) = map(int, input().split())
s = [0] * (n + 1)
ans = []
for i in range(q):
	(t, k, d) = map(int, input().split())
	sm = []
	for j in range(1, n + 1):
		if s[j] < t:
			sm.append(j)
			if len(sm) == k:
				break
	if len(sm) != k:
		ans.append('-1')
	else:
		ans.append(str(sum(sm)))
		for j in sm:
			s[j] = d + t - 1
print('\n'.join(ans))


while True:
	try:
		caption = input().split()
		n = int(caption[0])
		servers = [i for i in range(1, n + 1)]
		answer = []
		q = int(caption[1])
		using = {}
		for i in range(q):
			tasks = input().split()
			time = int(tasks[0])
			key = int(tasks[0]) + int(tasks[2])
			for i in list(using.keys()):
				if time >= i:
					servers += using[i]
					servers.sort()
					del using[i]
			need = int(tasks[1])
			touse = len(servers)
			if need > touse:
				answer.append(-1)
			else:
				amount = servers[:need]
				servers = servers[need:]
				sums = sum(amount)
				if not using.get(key):
					using[key] = amount
				else:
					using[key] += amount
				answer.append(sums)
		for i in answer:
			print(i)
	except EOFError:
		break


(cntServ, cntSurf) = list(map(int, input().split()))
ap = []
ap = [0] * (cntServ + 1)
l = 0
result = 0
for i in range(cntSurf):
	(num, cn, ter) = list(map(int, input().split()))
	arr = []
	for j in range(1, cntServ + 1):
		if ap[j] <= num:
			arr.append(j)
		if len(arr) == cn:
			break
	if len(arr) == cn:
		l = len(arr)
		print(sum(arr))
		for f in arr:
			ap[f] = num + ter
	else:
		print('-1')


f = lambda : map(int, input().split())
(n, m) = f()
s = [0] * n
for i in range(m):
	(t, k, d) = f()
	(j, p) = (0, [])
	while j < n and len(p) < k:
		if s[j] <= t:
			p.append(j)
		j += 1
	if len(p) < k:
		print(-1)
	else:
		for j in p:
			s[j] = t + d
		print(sum(p) + k)


(n, q) = list(map(int, input().split()))
servers = [i for i in range(1, n + 1)]
(res, used) = ([], {})
for i in range(q):
	(t, s, d) = list(map(int, input().split()))
	finish = t + d
	for i in list(used.keys()):
		if t >= i:
			servers += used[i]
			servers.sort()
			del used[i]
	if s > len(servers):
		res.append(-1)
		continue
	if not used.get(finish):
		used[finish] = servers[:s]
	else:
		used[finish] += servers[:s]
	res.append(sum(servers[:s]))
	servers = servers[s:]
for i in res:
	print(i)


(a, b) = map(int, input().split())
z = [0] * a
for _ in ' ' * b:
	(t, k, d) = map(int, input().split())
	gh = []
	for i in range(a):
		if z[i] < t:
			gh.append(i)
	if len(gh) < k:
		print(-1)
		continue
	for i in range(k):
		z[gh[i]] = t + d - 1
	print(sum(gh[:k]) + k)


(n, q) = [int(i) for i in input().split()]
available = [1 for i in range(n)]
for task in range(q):
	(t, k, d) = [int(i) for i in input().split()]
	assign = []
	len_assign = 0
	for i in range(n):
		if available[i] <= t:
			assign.append(i)
			len_assign += 1
		if len_assign >= k:
			break
	if len_assign >= k:
		for j in range(k):
			available[assign[j]] = t + d
		print(sum(assign) + k)
	else:
		print(-1)


import sys
input = sys.stdin.readline
(server, task) = list(map(int, input().split()))
serverstatus = [0] * server
for i in range(task):
	(moment, serven, time) = list(map(int, input().split()))
	ava = 0
	total = 0
	d = serverstatus[:]
	for i in range(server):
		if ava < serven and serverstatus[i] <= moment:
			ava += 1
			total += i + 1
			d[i] = moment + time
		elif ava == serven:
			break
	if ava < serven:
		print(-1)
	else:
		print(total)
		serverstatus = d[:]


import sys
input = sys.stdin.readline
(n, q) = map(int, input().split())
T = [0] * n
for _ in range(q):
	(t, k, d) = map(int, input().split())
	new_T = T[:]
	cnt = 0
	ans = 0
	for i in range(n):
		if new_T[i] < t:
			new_T[i] = t + d - 1
			cnt += 1
			ans += i + 1
		if cnt == k:
			break
	if cnt == k:
		T = new_T
		print(ans)
	else:
		print(-1)


(n, q) = map(int, input().split())
servers = [0 for i in range(n)]
for i in range(q):
	(t, k, d) = map(int, input().split())
	cnt = 0
	for server in servers:
		if server <= t:
			cnt += 1
			if cnt == k:
				break
	if cnt >= k:
		s = 0
		for i in range(n):
			if servers[i] <= t:
				servers[i] = t + d
				cnt -= 1
				s += i + 1
				if cnt == 0:
					break
		print(s)
	else:
		print(-1)


(n, q) = list(map(int, input().split()))
tasks = []
servers = [0] * n
for _ in range(q):
	tasks.append(tuple(map(int, input().split())))
for (t, k, d) in tasks:
	a = []
	for i in range(n):
		if t >= servers[i]:
			a.append(i)
	if len(a) >= k:
		total = 0
		for s in range(k):
			total += a[s] + 1
			servers[a[s]] = t + d
		print(total)
	else:
		print(-1)


num = [int(n) for n in input().split()]
server = [0 for n in range(0, num[0])]
result = list()
num_task = num[1]
temp_ti = 0
for i in range(0, num_task):
	temp_task = [int(n) for n in input().split()]
	time_passed = temp_task[0] - temp_ti
	temp_ti = temp_task[0]
	for n in range(0, num[0]):
		server[n] -= time_passed
		server[n] = 0 if server[n] < 0 else server[n]
	if server.count(0) < temp_task[1]:
		result.append(-1)
	else:
		accumulate_result = 0
		for i in range(0, num[0]):
			if not bool(server[i]):
				server[i] += temp_task[2]
				temp_task[1] -= 1
				accumulate_result += i + 1
			if temp_task[1] == 0:
				break
		result.append(accumulate_result)
for i in range(0, num_task):
	print(result[i])


(n, q) = list(map(int, input().split()))
servers = [0] * n
for _ in range(q):
	(t, k, d) = list(map(int, input().split()))
	free = []
	for sn in range(n):
		if servers[sn] < t:
			free.append(sn)
		if len(free) == k:
			break
	if len(free) < k:
		print(-1)
	else:
		for sn in free:
			servers[sn] = t + d - 1
		print(sum([x + 1 for x in free]))


p = input().rstrip().split(' ')
n = int(p[0])
q = int(p[1])
L = [0] * n
Q = []
W = []
S = []
D = []
for i in range(0, q):
	o = input().rstrip().split(' ')
	t = int(o[0])
	k = int(o[1])
	d = int(o[2])
	j = 0
	while len(S) > 0 and j < len(S):
		if S[j] <= t:
			R = W[j]
			del S[j]
			del W[j]
			for M in range(0, len(R)):
				L[R[M] - 1] = 0
		else:
			j += 1
	if L.count(0) >= k:
		E = []
		ans = 0
		for j in range(0, len(L)):
			if L[j] == 0 and k != 0:
				E.append(j + 1)
				ans += j + 1
				k -= 1
				L[j] = 1
		W.append(E)
		S.append(t + d)
		print(ans)
	else:
		print(-1)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def main():
	pass

def binary(n):
	return bin(n).replace('0b', '')

def decimal(s):
	return int(s, 2)

def pow2(n):
	p = 0
	while n > 1:
		n //= 2
		p += 1
	return p

def isPrime(n):
	if n == 1:
		return False
	else:
		root = int(n ** 0.5)
		root += 1
		for i in range(2, root):
			if n % i == 0:
				return False
		return True

def lts(l):
	s = ''.join(map(str, l))
	return s

def stl(s):
	l = list(s)
	return l

def sq(a, target, arr=[]):
	s = sum(arr)
	if s == target:
		return arr
	if s >= target:
		return
	for i in range(len(a)):
		n = a[i]
		remaining = a[i + 1:]
		ans = sq(remaining, target, arr + [n])
		if ans:
			return ans

def SieveOfEratosthenes(n):
	cnt = 0
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	for p in range(2, n + 1):
		if prime[p]:
			cnt += 1
	return cnt

def nCr(n, r):
	f = math.factorial
	return f(n) // f(r) // f(n - r)
mod = int(1000000000.0) + 7

def ssinp():
	return input()

def iinp():
	return int(input())

def nninp():
	return map(int, input().split())

def llinp():
	return list(map(int, input().split()))

def p(xyz):
	print(xyz)

def p2(a, b):
	print(a, b)
import math
from collections import OrderedDict
(n, q) = map(int, input().split())
nlist = list(range(1, n + 1))
l1 = 10 ** 6 + 1005
ind = 0
tlist = [[] for i in range(l1)]
for _ in range(q):
	ans = 0
	(t, k, d) = map(int, input().split())
	while True:
		if ind == l1 - 2:
			break
		if t >= ind:
			for i in tlist[ind]:
				nlist[i - 1] = i
			ind += 1
		else:
			break
		if ind == l1 - 2 or ind > t:
			break
	if k > n - nlist.count(0):
		print(-1)
	else:
		for i in range(n):
			if nlist[i] != 0:
				ans += nlist[i]
				tlist[t + d].append(nlist[i])
				nlist[i] = 0
				k = k - 1
			if k == 0:
				break
		print(ans)