Выбрав сторону Выживших, Эйден решает помочь им с подрывом ветряка фракции Миротворцев. Ветряк обладает определенным значением стабильности, изначально равным $$$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$$$ — номера ключевых элементов в том порядке, в котором их следует отключать.
Если существует несколько последовательностей отключения, приводящих к минимальной возможной стабильности, выведите любую из них.
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач, а также тесты из условия успешно пройдены.
Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи | Информация о проверке |
1 | 8 | $$$n \leqslant 8$$$ | полная | |
2 | 10 | $$$n \leqslant 20$$$; $$$b_i < 0$$$ для всех $$$i$$$ | полная | |
3 | 12 | существует единственный $$$i$$$, при котором $$$b_i < 0$$$ | полная | |
4 | 12 | $$$a_i = 0$$$ для всех $$$i$$$ | полная | |
5 | 16 | все отрицательные $$$b_i$$$ равны между собой | 2, 3 | полная |
6 | 20 | количество $$$i$$$, при которых $$$b_i < 0$$$, не больше $$$20$$$ | 1 – 3 | первая ошибка |
7 | 22 | нет | 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