Секретный бункер уходит на N этажей вниз. Под нижним этажом бункера находится сверхсекретная лаборатория. Злобный диверсант хочет вывести лабораторию из строя, залив её водой (даже очень небольшого количества воды хватит, чтобы запоганить сверхточные приборы). Для этого он использует лужицы воды, остающиеся от жизнедеятельности обитателей бункера. В лужицах i-го этажа находится Ei воды. Диверсанту известно, что если на нём скопится больше Сi воды, то перегородка не выдержит и вся вода сольется на этаж ниже. Он может проделать отверстия в некоторых перегородках, по которым вода также стечет вниз. Проделать отверстие в полу i-го этажа стоит Pi у.е. Помогите диверсанту уничтожить лабораторию с минимальными материальными затратами.
Входные данные
Первая строка содержит натуральное число N (1 <= N <= 50000) - количество этажей в бункере, в следующих N строках находятся тройки целых чисел C
i, E
i, P
i (0 < E
i <= Ci < 1000000; E
1+E
2+...+E
N < 2000000000; P
i > 0; P
1+P
2+...+P
N < 2000000000). Этажи нумеруются сверху вниз.
Выходные данные
В первой строке выдать количество денег, которое придется потратить злобному диверсанту, в следующих строках выведите номера этажей, в полу которых следует проделать отверстия.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10
7 3 10
2 2 14
1 1 15
13 10 7
55 1 5
7 7 4
7 2 6
91 8 2
10 1 6
20 5 14
|
6
6
8
|