Задача №113795. Развлечение с копьями
В Арифметическом университете иногда бывает так, что занятия по арифметике отменяются. Чтобы студенты не скучали без дела, для них организовали развлечение — метание копья. Для этого в комнате отдыха разместили автомат для продажи копий и мишень для метания.
Мишень состоит из нескольких слоёв, и каждое копьё при броске пробивает какое-то количество этих слоёв. Конечная цель — пробить мишень насквозь.
Каждое копьё характеризуется своими диаметром, прочностью и ценой. Автомат предлагает покупать копья по одному в определённой последовательности. Каждое предложенное копьё можно либо купить и сразу бросить в мишень, либо отказаться от его покупки, тогда автомат предлагает купить следующее копьё. После того, как автомат предожил для покупки все имеющиеся копья, он отключается.
Первое брошенное копьё оставляет в мишени круглую дыру с диаметром, равным диаметру брошенного копья, и глубиной, равной прочности брошенного копья. Каждое следующее копьё бросается точно в центр образованной дыры. Если диаметр этого копья не превосходит диаметров всех предыдущих брошенных в мишень копий, то оно продолжает пробивать слои мишени, начиная с первого слоя, в котором пока нет дыры. Иначе оно начинает пробивать слои, начиная с того слоя, диаметр дыры в котором строго меньше диаметра копья.
Копьё пробивает количество слоёв равное своей прочности. Количество пробитых слоёв не зависит от того, были ли они уже пробиты ранее копьём меньшего диаметра. Если копьё имеет достаточную прочность, чтобы пробить последний слой мишени, оно пролетает мишень насквозь и игра завершается.
Вам известна последовательность, в которой автомат предлагает купить копья. Определите какие копья нужно купить и бросить, чтобы пробить все слои мишени, заплатив при этом минимальную возможную сумму.
В первой строке даны два целых числа n и m — количество копий в автомате и количество слоёв мишени (1 ≤ n, m ≤ 2000).
В следующих n строках описаны копья. В i-й из этих строк даны три числа di, ci и pi — диаметр, прочность и цена i-го копья в последовательности, предлагаемой автоматом (1 ≤ di, pi ≤ 109; 1 ≤ ci ≤ 2000).
В первой строке выведите два целых числа s и k — суммарную цену копий в оптимальном наборе и их количество. В следующей строке выведите k целых чисел — номера взятых копий. Номера следует выводить в возрастающем порядке, именно в этом порядке копья будут куплены и брошены в мишень.
Если не существует подходящего набора, выведите одно число « - 1». Если существует несколько наборов копий с минимальной суммарной ценой, выведите любой из них.
2 2
1 1 1
2 3 2
2 1
2
2 4
1 1 1
2 3 2
-1
2 4
1 1 1
1 3 2
3 2
1 2