← 返回题目列表

Codeforces · 747/C

C. 服务器

中文机器翻译题面 查看原题

实验室中有n台服务器,每台服务器都可以执行任务。每个服务器都有一个唯一的 ID——从 1 到 n 的整数。

已知一天中将有 q 个任务出现,其中第 i 个任务由三个整数表示:ti - 任务出现的时刻(以秒为单位),ki - 执行该任务所需的服务器数量,di - 执行该任务所需的时间(以秒为单位)。所有的 ti 都是不同的。

要执行第 i 个任务,您需要在第二个 ti 中未占用的 ki 服务器。服务器开始执行任务后,每个服务器将在接下来的 di 秒内忙碌。因此,它们将在 ti, ti + 1, ..., ti + di - 1 秒内变得繁忙。为了执行任务,将从所有未占用的服务器中选择具有最小 id 的 ki 服务器。如果在第二个 ti 中没有足够的空闲服务器,则该任务将被忽略。

编写程序来确定哪些任务将被执行,哪些任务将被忽略。

输入

第一行包含两个正整数 n 和 q (1 ≤ n ≤ 100, 1 ≤ q ≤ 105) — 服务器数量和任务数量。

接下来 q 行每行包含三个整数,第 i 行包含整数 ti、ki 和 di (1 ≤ ti ≤ 106, 1 ≤ ki ≤ n, 1 ≤ di ≤ 1000) - 第 i 个任务到来的时刻(以秒为单位)、执行该任务所需的服务器数量以及执行该任务所需的时间(以秒为单位)。任务按时间顺序给出,并且将在不同的秒内完成。

输出

打印 q 行。如果第 i 个任务将由服务器执行,则在第 i 行中打印将执行此任务的服务器 id 的总和。否则,打印-1。

示例

输入 #1

4 3
1 3 2
2 2 1
3 4 3

输出 #1

6
-1
10

输入 #2

3 2
3 2 3
5 1 2

输出 #2

3
3

输入 #3

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

输出 #3

6
9
30
-1
15
36

注意

在第二个 1 的第一个示例中,第一个任务将会出现,它将在 id 为 1、2 和 3(id 之和等于 6)的服务器上执行两秒。在第二个 2 中,第二个任务将会到来,它将被忽略,因为此时只有服务器 4 未被占用。在第二个3中,第三个任务将会到来。此时,id为1、2、3的服务器将再次空闲,因此第三个任务将在所有id为1、2、3、4的服务器上执行(id之和为10)。

在第二个 3 的第二个示例中,第一个任务将会出现,它将在 id 为 1 和 2(id 之和为 3)的服务器上执行三秒。在第二个 5 中,第二个任务将会到来,它将在服务器 3 上执行,因为前两个服务器将忙于执行第一个任务。