| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 30 | 9 | 3 | 30.000% |
Выбрав сторону Выживших, Эйден решает помочь им с подрывом ветряка фракции Миротворцев. Ветряк обладает определенным значением стабильности, изначально равным $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$ --- номера ключевых элементов в том порядке, в котором их следует отключать.
Если существует несколько последовательностей отключения, приводящих к минимальной возможной стабильности, выведите любую из них.
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