Remote Training on Programming

Многие вузы переходят на рейтинговую систему оценки: оценки студентов зависят от того, как они сдают задания в течение всего семестра. Для каждого задания устанавливается срок сдачи, позже которого задание не принимается.

Один студент получил N заданий утром дня с номером 1.

• Студенту потребуется ровно L_i дней, чтобы выполнить задание с номером i.
• Если студент берётся за какое-либо задание, то он ни на что не будет отвлекаться, пока его не выполнит.
• Начав работать над заданием в день с номером x, студент закончит и сдаст его в день с номером x + L_i − 1. Силы взяться за новое задание будут у него только на следующий день.
• Задание с номером i не будет принято, если оно будет сдано позже, чем в день с номером D_i.
• Рейтинг студента увеличится на R_i баллов после сдачи задания с номером i.

Студент хочет, чтобы его рейтинг стал как можно выше. Напишите программу, которая, получив информацию о заданиях, определит, какие задания и в каком порядке должен выполнять студент, чтобы максимально повысить свой рейтинг.

Рекомендуется рассмотреть частичные решения

• N ≤ 2
• L₁ = L₂ = …= L_N = 1
• D₁ = D₂ = …= D_N

Формат входного файла

Входной файл содержит целое число N, за которым следует N троек целых чисел L_i D_i R_i — информация о заданиях.

Формат выходного файла

Программа должна вывести в выходной файл максимальное количество баллов, которое может заработать студент, а затем — описания заданий, которые ему нужно для этого выполнить. Каждое описание состоит из чисел k_i s_i — порядкового номера задания и номера дня, когда студенту нужно начать его выполнение. Все k_i должны быть различны. Задания должны быть выведены в порядке возрастания s_i.

Если студент не сможет заработать ни одного балла, вывести единственное число 0.

Если существует несколько способов заработать максимальное количество баллов, вывести любой из них.

Ограничения

1 ≤ N ≤ 1000; 1 ≤ L_i, D_i, R_i ≤ 1000

Примеры тестов

5

7 8 6

2 2 1

5 8 4

3 9 3

2 5 1

7

3 1

4 6