Многие вузы переходят на рейтинговую систему оценки: оценки студентов
зависят от того, как они сдают задания в течение всего семестра. Для
каждого задания устанавливается срок сдачи, позже которого задание не
принимается.
Один студент получил N заданий утром дня с
номером 1.
- Студенту потребуется ровно Li дней,
чтобы выполнить задание с номером i.
- Если студент берётся за
какое-либо задание, то он ни на что не будет отвлекаться, пока его не
выполнит.
- Начав работать над заданием
в день с номером x,
студент закончит и сдаст его в день с номером x + Li − 1. Силы взяться за новое задание будут у него только на
следующий день.
- Задание с номером i не будет принято, если
оно будет сдано позже, чем в день с номером Di.
- Рейтинг студента увеличится
на Ri
баллов после сдачи задания с номером i.
Студент хочет, чтобы его рейтинг стал как можно выше. Напишите программу,
которая, получив информацию о заданиях, определит, какие задания и в каком
порядке должен выполнять студент, чтобы максимально повысить свой рейтинг.
Рекомендуется рассмотреть частичные решения
- N ≤ 2
- L1 = L2 = …= LN = 1
- D1 = D2 = …= DN
Формат входного файла
Входной файл содержит целое число N, за
которым следует N троек целых чисел Li
Di Ri
— информация о заданиях.
Формат выходного файла
Программа должна вывести в выходной файл максимальное количество баллов,
которое может заработать студент, а затем — описания заданий, которые ему нужно
для этого выполнить. Каждое описание состоит из чисел ki si — порядкового номера задания и
номера дня, когда студенту нужно начать его выполнение. Все ki должны быть различны. Задания
должны быть выведены в порядке возрастания si.
Если студент не сможет заработать ни одного балла, вывести единственное
число 0.
Если существует несколько способов заработать максимальное количество
баллов, вывести любой из них.
Ограничения
1 ≤ N ≤ 1000; 1 ≤ Li, Di,
Ri ≤ 1000
Примеры тестов
|
№
|
Входной файл
|
Выходной файл
|
|
1
|
5
7 8 6
2 2 1
5 8 4
3 9 3
2 5 1
|
7
3 1
4 6
|
