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

Выбрав сторону Выживших, Эйден решает помочь им с подрывом ветряка фракции Миротворцев. Ветряк обладает определенным значением стабильности, изначально равным $$$s$$$. Чем меньше станет его стабильность, тем проще будет его подорвать.

У ветряка также есть $$$n$$$ ключевых элементов, доступ к $$$i$$$-му из которых можно получить только если текущая стабильность ветряка не меньше $$$a_i$$$. При этом, имея доступ к $$$i$$$-му ключевому элементу, Эйден может отключить его, тем самым изменив стабильность ветряка ровно на $$$b_i$$$ (если $$$b_i$$$ отрицательно, то стабильность уменьшается, а если положительно — увеличивается).

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

Помогите Эйдену определить, какое минимальное значение стабильности ветряка можно получить, и какие ключевые элементы в каком порядке для этого стоит отключать.

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

В первой строке ввода через пробел даны два целых числа $$$n$$$ и $$$s$$$ — количество ключевых элементов и изначальное значение стабильности ($$$1 \leqslant n \leqslant 1000$$$; $$$0 \leqslant s \leqslant 10^4$$$).

В следующих $$$n$$$ строках перечислены описания ключевых элементов. В $$$i$$$-й из них через пробел даны два целых числа $$$a_i$$$ и $$$b_i$$$ — порог стабильности, начиная с которого элемент доступен, и изменение стабильности при отключении этого элемента ($$$0 \leqslant a_i \leqslant 2 \cdot 10^4$$$; $$$-10^4 \leqslant b_i \leqslant 10^4$$$).

Гарантируется, что $$$\sum\limits_{i=1}^n \left| b_i \right| \leqslant 2 \cdot 10^4$$$.

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

В первой строке выведите через пробел два целых числа $$$ans$$$ и $$$k$$$ — минимальную возможную конечную стабильность после отключения каких-то элементов, и сколько элементов нужно отключить для такого результата.

В следующей строке выведите через пробел $$$k$$$ различных целых чисел от $$$1$$$ до $$$n$$$ — номера ключевых элементов в том порядке, в котором их следует отключать.

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

Система оценки

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

ПодзадачаБаллы Дополнительные ограничения Необходимые подзадачи Информация о проверке
18$$$n \leqslant 8$$$полная
210 $$$n \leqslant 20$$$; $$$b_i < 0$$$ для всех $$$i$$$ полная
312 существует единственный $$$i$$$, при котором $$$b_i < 0$$$ полная
412$$$a_i = 0$$$ для всех $$$i$$$полная
516 все отрицательные $$$b_i$$$ равны между собой 2, 3полная
620 количество $$$i$$$, при которых $$$b_i < 0$$$, не больше $$$20$$$ 1 – 3первая ошибка
722нет1 – 6первая ошибка

Примеры

Входные данные
3 10
10 -2
10 6
15 -9
Выходные данные
7 2
2 3 
Входные данные
5 100
180 20
100 79
179 -80
180 -90
1 1
Выходные данные
90 3
5 2 4 
Входные данные
3 50
50 -30
30 -40
40 -20
Выходные данные
-10 2
3 2