{"raw_statement":[{"iden":"statement","content":"There are _n_ servers in a laboratory, each of them can perform tasks. Each server has a unique id — integer from 1 to _n_.\n\nIt 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.\n\nTo 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.\n\nWrite the program that determines which tasks will be performed and which will be ignored."},{"iden":"input","content":"The first line contains two positive integers _n_ and _q_ (1 ≤ _n_ ≤ 100, 1 ≤ _q_ ≤ 105) — the number of servers and the number of tasks.\n\nNext _q_ lines contains three integers each, the _i_\\-th line contains integers _t__i_, _k__i_ and _d__i_ (1 ≤ _t__i_ ≤ 106, 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."},{"iden":"output","content":"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_."},{"iden":"examples","content":"Input\n\n4 3\n1 3 2\n2 2 1\n3 4 3\n\nOutput\n\n6\n-1\n10\n\nInput\n\n3 2\n3 2 3\n5 1 2\n\nOutput\n\n3\n3\n\nInput\n\n8 6\n1 3 20\n4 2 1\n6 5 5\n10 1 1\n15 3 6\n21 8 8\n\nOutput\n\n6\n9\n30\n-1\n15\n36"},{"iden":"note","content":"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).\n\nIn 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."}],"translated_statement":[{"iden":"statement","content":"实验室中有 #cf_span[n] 台服务器，每台都可以执行任务。每台服务器有一个唯一编号 —— 从 #cf_span[1] 到 #cf_span[n] 的整数。\n\n已知一天内将有 #cf_span[q] 个任务到达，第 #cf_span[i] 个任务由三个整数描述：#cf_span[ti] —— 任务到达的时刻（秒），#cf_span[ki] —— 执行该任务所需的服务器数量，以及 #cf_span[di] —— 执行该任务所需的时间（秒）。所有 #cf_span[ti] 互不相同。\n\n要执行第 #cf_span[i] 个任务，你需要在第 #cf_span[ti] 秒时有 #cf_span[ki] 台空闲的服务器。当服务器开始执行任务后，它们将在接下来的 #cf_span[di] 秒内保持忙碌，即在秒数 #cf_span[ti, ti + 1, ..., ti + di - 1] 内处于忙碌状态。执行任务时，将从所有空闲服务器中选择编号最小的 #cf_span[ki] 台服务器。如果在第 #cf_span[ti] 秒时空闲服务器不足，则该任务被忽略。\n\n编写一个程序，确定哪些任务会被执行，哪些会被忽略。\n\n第一行包含两个正整数 #cf_span[n] 和 #cf_span[q] (#cf_span[1 ≤ n ≤ 100], #cf_span[1 ≤ q ≤ 105]) —— 服务器数量和任务数量。\n\n接下来的 #cf_span[q] 行，每行包含三个整数，第 #cf_span[i] 行包含整数 #cf_span[ti], #cf_span[ki] 和 #cf_span[di] (#cf_span[1 ≤ ti ≤ 106], #cf_span[1 ≤ ki ≤ n], #cf_span[1 ≤ di ≤ 1000]) —— 第 #cf_span[i] 个任务到达的时刻、所需服务器数量和执行所需时间。任务按时间顺序给出，且到达时刻互不相同。\n\n请输出 #cf_span[q] 行。如果第 #cf_span[i] 个任务被服务器执行，请在第 #cf_span[i] 行输出执行该任务的服务器编号之和；否则，输出 _-1_。\n\n在第一个示例中，第 #cf_span[1] 秒时第一个任务到达，它将在编号为 #cf_span[1]、#cf_span[2] 和 #cf_span[3] 的服务器上执行（编号之和为 #cf_span[6]），持续两秒。第 #cf_span[2] 秒时第二个任务到达，它将被忽略，因为此时仅有服务器 #cf_span[4] 空闲。第 #cf_span[3] 秒时第三个任务到达，此时编号为 #cf_span[1]、#cf_span[2] 和 #cf_span[3] 的服务器已再次空闲，因此第三个任务将在所有编号为 #cf_span[1]、#cf_span[2]、#cf_span[3] 和 #cf_span[4] 的服务器上执行（编号之和为 #cf_span[10]）。\n\n在第二个示例中，第 #cf_span[3] 秒时第一个任务到达，它将在编号为 #cf_span[1] 和 #cf_span[2] 的服务器上执行（编号之和为 #cf_span[3]），持续三秒。第 #cf_span[5] 秒时第二个任务到达，它将在服务器 #cf_span[3] 上执行，因为前两台服务器正忙于执行第一个任务。"},{"iden":"input","content":"第一行包含两个正整数 #cf_span[n] 和 #cf_span[q] (#cf_span[1 ≤ n ≤ 100], #cf_span[1 ≤ q ≤ 105]) —— 服务器数量和任务数量。接下来的 #cf_span[q] 行，每行包含三个整数，第 #cf_span[i] 行包含整数 #cf_span[ti], #cf_span[ki] 和 #cf_span[di] (#cf_span[1 ≤ ti ≤ 106], #cf_span[1 ≤ ki ≤ n], #cf_span[1 ≤ di ≤ 1000]) —— 第 #cf_span[i] 个任务到达的时刻、所需服务器数量和执行所需时间。任务按时间顺序给出，且到达时刻互不相同。"},{"iden":"output","content":"请输出 #cf_span[q] 行。如果第 #cf_span[i] 个任务被服务器执行，请在第 #cf_span[i] 行输出执行该任务的服务器编号之和；否则，输出 _-1_。"},{"iden":"examples","content":"输入\n4 3\n1 3 2\n2 2 1\n3 4 3\n输出\n6\n-1\n10\n\n输入\n3 2\n3 2 3\n5 1 2\n输出\n3\n3\n\n输入\n8 6\n1 3 20\n4 2 1\n6 5 5\n10 1 1\n15 3 6\n21 8 8\n输出\n6\n9\n30\n-1\n15\n36"},{"iden":"note","content":"在第一个示例中，第 #cf_span[1] 秒时第一个任务到达，它将在编号为 #cf_span[1]、#cf_span[2] 和 #cf_span[3] 的服务器上执行（编号之和为 #cf_span[6]），持续两秒。第 #cf_span[2] 秒时第二个任务到达，它将被忽略，因为此时仅有服务器 #cf_span[4] 空闲。第 #cf_span[3] 秒时第三个任务到达，此时编号为 #cf_span[1]、#cf_span[2] 和 #cf_span[3] 的服务器已再次空闲，因此第三个任务将在所有编号为 #cf_span[1]、#cf_span[2]、#cf_span[3] 和 #cf_span[4] 的服务器上执行（编号之和为 #cf_span[10]）。\n\n在第二个示例中，第 #cf_span[3] 秒时第一个任务到达，它将在编号为 #cf_span[1] 和 #cf_span[2] 的服务器上执行（编号之和为 #cf_span[3]），持续三秒。第 #cf_span[5] 秒时第二个任务到达，它将在服务器 #cf_span[3] 上执行，因为前两台服务器正忙于执行第一个任务。"}],"sample_group":[],"show_order":[],"formal_statement":"Let $ n $ be the number of servers, indexed from $ 1 $ to $ n $.  \nLet $ q $ be the number of tasks.  \n\nEach task $ i $ (for $ i = 1, 2, \\dots, q $) is characterized by a triplet $ (t_i, k_i, d_i) $, where:  \n- $ t_i \\in \\mathbb{Z}^+ $: the arrival time (in seconds),  \n- $ k_i \\in \\mathbb{Z}^+ $: the number of servers required,  \n- $ d_i \\in \\mathbb{Z}^+ $: the duration of the task (in seconds).  \n\nDefine a set $ B \\subseteq \\{1, 2, \\dots, n\\} \\times \\mathbb{Z}^+ $ to represent busy servers:  \nEach element $ (s, e) \\in B $ means server $ s $ is busy until (but not including) time $ e $.  \n\nAt time $ t_i $, the set of available servers is:  \n$$\nA_i = \\left\\{ s \\in \\{1, 2, \\dots, n\\} \\mid \\forall (s', e) \\in B, \\; s' = s \\implies e \\leq t_i \\right\\}\n$$\n\nLet $ A_i $ be sorted in increasing order.  \nIf $ |A_i| \\geq k_i $, then the task is assigned to the first $ k_i $ servers in $ A_i $:  \n$$\nS_i = \\{ a_1, a_2, \\dots, a_{k_i} \\}, \\quad \\text{where } a_1 < a_2 < \\dots < a_{k_i} \\text{ are the smallest } k_i \\text{ servers in } A_i\n$$\n\nThe sum of server IDs is:  \n$$\n\\text{sum}_i = \\sum_{s \\in S_i} s\n$$\n\nThen, update the busy set:  \n$$\nB \\leftarrow B \\cup \\{ (s, t_i + d_i) \\mid s \\in S_i \\}\n$$\n\nOtherwise, if $ |A_i| < k_i $, the task is ignored, and $ \\text{sum}_i = -1 $.  \n\n**Input:**  \n- $ n, q $  \n- Sequence of $ q $ tasks $ (t_i, k_i, d_i) $, with $ t_1 < t_2 < \\dots < t_q $  \n\n**Output:**  \nFor each task $ i $, output $ \\text{sum}_i $ if assigned, else $ -1 $.","simple_statement":null,"has_page_source":false}