Подрыв ветряка

시간 제한1초메모리 제한1024 MB

요약

각 요소에 접근에 필요한 안정성 임계값과 안정성 변화량이 주어질 때, 도달 가능한 최소 안정성과 그 순서를 구한다.

난이도: 보통10점 중 7점
유형: 그리디, 동적 계획법
정답자: 아직 제출이 없습니다

문제

Выбрав сторону Выживших, Эйден решает помочь им с подрывом ветряка фракции Миротворцев. Ветряк обладает определенным значением стабильности, изначально равным $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

예제 1
입력
```
3 10
10 -2
10 6
15 -9
```
예상 출력
```
7 2
2 3
```

예제 2

입력

예상 출력

90 3
5 2 4

예제 3
입력
```
3 50
50 -30
30 -40
40 -20
```
예상 출력
```
-10 2
3 2
```