Олимпиадный тренинг

Задача . C. Серверы

Задача

В лаборатории есть n серверов, каждый из которых может выполнять задания. Серверы пронумерованы уникальными целыми числоми от 1 до n.

Известно, что в течение суток поступит q заданий, i-е из которых характеризуется тремя величинами: t_i — секунда поступления задания, k_i — количество серверов, которые нужны для его выполнения, а также d_i — продолжительность выполнения этого задания в секундах. Все t_i — различны.

Для того, чтобы выполнить i-е пришедшее задание, нужно k_i серверов, которые должны быть свободны в секунду t_i. После начала выполнения задания каждый из них будет занят в течение ближайших d_i секунд. Таким образом, они будут заняты в секунды t_i, t_i + 1, ..., t_i + d_i - 1. Из всех свободных серверов для выполнения будут выбраны k_i серверов с наименьшими номерами. Если в секунду t_i не хватает свободных серверов, то задание будет проигнорировано.

Напишите программу, определяющую, какие задания будут выполнены серверами, а какие будут проигнорированы.

Входные данные

В первой строке следует два целых положительных числа n и q (1 ≤ n ≤ 100, 1 ≤ q ≤ 10⁵) — количество серверов и количество заданий.

В каждой из следующих q строк записаны по три целых числа, в i-й из них записаны целые числа t_i, k_i и d_i (1 ≤ t_i ≤ 10⁶, 1 ≤ k_i ≤ n, 1 ≤ d_i ≤ 1000) — секунда поступления i-го задания, количество серверов, необходимых для его выполнения, а также время выполнения этого задания. Задания заданы в хронологическом порядке, и все они поступят в разные секунды.

Выходные данные

Выведите q строк. Если i-е задание будет принято на выполнение, выведите в i-й строке сумму номеров серверов, на которых будет выполняться это задание. В противном случае выведите -1.

Примечание

В первом примере в секунду 1 придет первое задание, которое будет выполняться на серверах с номерами 1, 2 и 3 (сумма номеров равна 6) в течение двух секунд. В секунду 2 поступит второе задание, которое будет проигнорировано, так как в эту секунду будет свободен только сервер номер 4. В секунду 3 придет третье задание. К этому времени как раз освободятся серверы с номерами 1, 2 и 3, поэтому третье задание будет выполняться на всех имеющихся серверах с номерами 1, 2, 3 и 4 (сумма номеров равна 10).

В втором примере в секунду 3 придет первое задание, которое будет выполняться на серверах с номерами 1 и 2 (сумма равна 3) в течение трех секунд. В секунду 5 поступит второе задание, которое будет выполняться на сервере номер 3, так как первые два сервера будут заняты выполнением первого задания.

Примеры

№	Входные данные	Выходные данные
1	4 3 1 3 2 2 2 1 3 4 3	6 -1 10
2	3 2 3 2 3 5 1 2	3 3
3	8 6 1 3 20 4 2 1 6 5 5 10 1 1 15 3 6 21 8 8	6 9 30 -1 15 36

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам

	Кол-во
С++ Mingw-w64	5

Комментарий учителя

Ваш ответ

выберите язык и введите исходный код

Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!

Загруженные файлы

Нет