D. Не бойтесь, ДравДэ добрый
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Колонна из n грузовиков, направляющаяся из города «Z» в город «З» подошла к туннелю, известному, как туннель Ужаса. Страшные слухи ходили среди водителей грузовиков о монстре ДравДэ, который охотится в этом туннеле. Некоторые водители боялись ехать первыми, некоторые последними, но рассмотрим более общий случай. Каждый грузовик характеризуется четырьмя числами:

  • v — ценность этого грузовика, его пассажиров и груза
  • c — количество пассажиров в грузовике, считая водителя
  • l — суммарное количество человек, которое должно ехать впереди этого грузовика, чтобы водитель смог побороть страх («если монстр появится спереди, то он съест сначала их»)
  • r — суммарное количество человек, которое должно ехать позади этого грузовика, чтобы водитель смог побороть страх («если монстр появится сзади, то он съест сначала их»).

Так как дорога узкая, то от появления ДравДэ сбоку никак не спастись. Более того, нельзя даже перестроить колонну. Относительный порядок машин изменить невозможно, но можно любую машину убрать из колонны, оставив её перед туннелем на неопределенный срок. Ваша задача, как начальника колонны, состоит в том, чтобы убрать некоторые грузовики так, чтобы оставшаяся колонна могла ехать и сумма ценностей проехавших грузовиков была максимальна.

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

В первой строке входного файла задано целое число n (1 ≤ n ≤ 105) — количество грузовиков в колонне. В следующих n строках содержится по четыре числа. Числа в i-той строке: vi, ci, li, ri (1 ≤ vi ≤ 104, 1 ≤ ci ≤ 105, 0 ≤ li, ri ≤ 105) — описывают i-й грузовик. Грузовики нумеруются с 1, считая от головы колонны.

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

В первой строке выведите число k — количество грузовиков, которые проедут через туннель. Во второй строке выведите k чисел — номера этих грузовиков в порядке возрастания. Не забудьте, что относительный порядок грузовиков менять нельзя. Если решений несколько, выведите любое.

Примеры
Входные данные
5
1 1 0 3
1 1 1 2
1 1 2 1
1 1 3 0
2 1 3 0
Выходные данные
4
1 2 3 5
Входные данные
5
1 1 0 3
10 1 2 1
2 2 1 1
10 1 1 2
3 1 3 0
Выходные данные
3
1 3 5