E. Пожар
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Поликарпа беда — пожар! Время спасать самое ценное. Поликарп оценил, что на спасение вещи i ему потребуется ti секунд времени. Кроме того, для каждой вещи он оценил величину di — время, через которое вещь i сгорит и больше не будет представлять какую-либо ценность. В частности, если ti ≥ di, то вещь i спасти невозможно.

Зная ценность pi каждой из вещей, найдите такой набор вещей, что Поликарп сможет спасти все эти вещи, и при этом суммарная ценность спасённых вещей будет максимальной. Спасение вещей происходит последовательно. Например, если он спасает сначала вещь a, а потом b, то вещь a будет спасена через ta секунд, а вещь b через ta + tb секунд.

Входные данные

В первой строке следует целое число n (1 ≤ n ≤ 100) — количество вещей Поликарпа.

В следующих n строках следуют по три целых числа ti, di, pi (1 ≤ ti ≤ 20, 1 ≤ di ≤ 2 000, 1 ≤ pi ≤ 20) — время, необходимое для спасения вещи i, время, через которое сгорит вещь i, и ценность вещи i.

Выходные данные

В первую строку выведите максимальную возможную суммарную ценность набора спасенных вещей. Во вторую строку выведите целое число m — количество вещей в искомом наборе. В третью строку выведите m различных целых чисел — номера спасенных вещей в порядке их спасения. Вещи нумеруются, начиная с единицы, в том же порядке, в котором они заданы во входных данных. Если ответов несколько, разрешается вывести любой из них.

Примеры
Входные данные
3
3 7 4
2 6 5
3 7 6
Выходные данные
11
2
2 3
Входные данные
2
5 6 1
3 3 5
Выходные данные
1
1
1
Примечание

В первом примере Поликарп успеет спасти любые две вещи, но, чтобы максимизировать ценность спасённых вещей, он должен спасти вторую и третью вещь. Например, он может сначала спасти третью вещь через 3 секунды, а затем ещё через 2 секунды спасти вторую вещь. Таким образом, суммарная ценность спасённых вещей будет равна 6 + 5 = 11.

Во втором примере Поликарп успеет спасти только первую вещь, так как даже если он сразу начнёт спасать вторую вещь, то к тому моменту, когда ему удастся её спасти (через 3 секунды), она уже полностью сгорит.