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: interview

Starter code:

Solutions:
n, q = list(map(int, input().split()))
servers = [0] * n
for _ in range(q):
    t, k, d = list(map(int, input().split()))
    # free = [i for i, x in enumerate(servers) if x < t]
    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]))


import math
import sys

def solve(n, q):
    servers = [0] * n
    res = [None]*q
    for j, line in enumerate(sys.stdin):
        t, k, d = list(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 = list(map(int, input().split()))
print('\n'.join(map(str, solve(n, q))))
    


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)

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]
    ###length
    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])


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
#
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 = 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 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))


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)

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



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=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))

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)))



import heapq as pq

from sys import stdin, stdout



#Heap method written by Engineermind.cho

#Testing if heap + fast IO can make python pass this question



n, q = list(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 = list(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:

        stdout.write('-1\n')

        continue

    else:

        stdout.write(str(sum(server[:k]))+'\n')

        if d != 1:

            pq.heappush(running, (t+d, server[:k].copy()))

            server = server[k:]



# Made By Mostafa_Khaled


from collections import defaultdict
n, q = list(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 = list(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



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)


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 = 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)


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)

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)