Задача C. Консервативная стратегия
Задачу добавил: alef
Успешно сдано решений: 191
Почти все министры согласились, что строительство должно развернуться на берегу реки, и строить надо не просто стадион, а спортивно-туристический комплекс. Да только как всегда не ко времени министр промышленности Силантий слово вставил.
Что комплекс — сооружение тяжёлое, берег реки укреплять придётся. Что коммуникации в той части царства не выдержат увеличившейся в несколько раз нагрузки, а это ещё дополнительные вложения. Даже большое количество строительных материалов завезти — и то проблема, мало какие дороги в царстве выдержат постоянное движение тяжёлой техники. К тому же работы можно только в тёплое время года вести, значит, придётся тратить время и деньги на консервацию сооружения.
Строительство состоит из 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