Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 






Задача C. Консервативная стратегия

Задачу добавил: alef

Успешно сдано решений: 163

Ограничение по времени на тест:2 секунды
Ограничение по памяти на тест:256 мегабайт

Почти все министры согласились, что строительство должно развернуться на берегу реки, и строить надо не просто стадион, а спортивно-туристический комплекс. Да только как всегда не ко времени министр промышленности Силантий слово вставил.

Что комплекс — сооружение тяжёлое, берег реки укреплять придётся. Что коммуникации в той части царства не выдержат увеличившейся в несколько раз нагрузки, а это ещё дополнительные вложения. Даже большое количество строительных материалов завезти — и то проблема, мало какие дороги в царстве выдержат постоянное движение тяжёлой техники. К тому же работы можно только в тёплое время года вести, значит, придётся тратить время и деньги на консервацию сооружения.

Строительство состоит из n этапов. Для каждого этапа известна его длительность dj единиц времени. Менять этапы местами нельзя.

Строительство можно непрерывно вести в течение t единиц времени, после чего в силу погодных условий его придется приостановить. Будем называть это время сезоном. Строительство можно приостановить и раньше, чем истекут t единиц времени (т.е. раньше, чем завершится сезон).

Если этап #j не был завершён в течение сезона, придётся потратить время cj на консервацию сооружения.

После наступления нового сезона у строителей вновь будет возможность работать в течение t единиц времени. Если сооружение находится в законсервированном состоянии, то сначала нужно провести его расконсервацию. На расконсервацию потребуется uj единиц времени, если консервация производилась в течение этапа #j.

И консервация, и расконсервация могут проводиться только в течение сезона.

Ваша задача — определить минимальное количество сезонов, необходимых, чтобы построить сооружение.

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

В первой строке содержатся целые числа n и t (1 ≤ n ≤ 100,  1 ≤ t ≤ 105).

В каждой из следующих n строк содержится по 3 целых числа dj,  cj,  uj (1 ≤ dj,  cj,  uj ≤ 105,  j = 1, 2, ..., n) — длительность этапа #j, время, необходимое на консервацию сооружения, находящегося на этапе #j, время, необходимое на расконсервацию сооружения, законсервированного на этапе #j.

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

В первой строке выведите единственное целое число s — минимально возможное количество сезонов, которое потребуется, чтобы завершить строительство.

Если завершить строительство нельзя, выведите  - 1.

Если завершить строительство можно, и количество сезонов не превышает 105, выведите также s строк. В каждой строке выведите этапы, на которых велось строительство в течение этого сезона.

Система оценки

Подзадача 1 (до 30 очков)

n ≤ 20;

dj,  cj,  uj < t (j = 1, 2, ..., n).

Баллы начисляются за каждый пройденный тест.

Подзадача 2 (до 70 очков)

n ≤ 100.

Баллы начисляются, если пройдены все тесты в группе.

По запросу сообщается результат проверки на каждом тесте.

Примеры

Входные данные
5 10
4 6 3
3 1 7
5 3 2
7 2 2
4 2 5
Выходные данные
3
1 2
3 4
4 5
Входные данные
3 8
5 6 4
10 2 2
10 4 7
Выходные данные
-1

Сдать задачу

Задать вопрос жюри по этой задаче