У Поликарпа беда — пожар! Время спасать самое ценное. Поликарп оценил, что на спасение вещи i ему потребуется ti секунд времени. Кроме того, для каждой вещи он оценил величину di — время, через которое вещь i сгорит и больше не будет представлять какую-либо ценность. В частности, если ti ≥ di, то вещь i спасти невозможно.
Зная ценность pi каждой из вещей, найдите такой набор вещей, что Поликарп сможет спасти все эти вещи, и при этом суммарная ценность спасённых вещей будет максимальной. Спасение вещей происходит последовательно. Например, если он спасает сначала вещь a, а потом b, то вещь a будет спасена через ta секунд, а вещь b через ta + tb секунд.
Выходные данные
В первую строку выведите максимальную возможную суммарную ценность набора спасенных вещей. Во вторую строку выведите целое число m — количество вещей в искомом наборе. В третью строку выведите m различных целых чисел — номера спасенных вещей в порядке их спасения. Вещи нумеруются, начиная с единицы, в том же порядке, в котором они заданы во входных данных. Если ответов несколько, разрешается вывести любой из них.
Примечание
В первом примере Поликарп успеет спасти любые две вещи, но, чтобы максимизировать ценность спасённых вещей, он должен спасти вторую и третью вещь. Например, он может сначала спасти третью вещь через 3 секунды, а затем ещё через 2 секунды спасти вторую вещь. Таким образом, суммарная ценность спасённых вещей будет равна 6 + 5 = 11.
Во втором примере Поликарп успеет спасти только первую вещь, так как даже если он сразу начнёт спасать вторую вещь, то к тому моменту, когда ему удастся её спасти (через 3 секунды), она уже полностью сгорит.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3 7 4
2 6 5
3 7 6
|
11
2
2 3
|
|
2
|
2
5 6 1
3 3 5
|
1
1
1
|