Ограничения: время – 300ms/600ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Отряд имперских инквизиторов планирует операцию против группы из `N` еретиков, про каждого из которых известны его сила `S` (насколько он опасен в бою) и убежденность `V` (насколько он тверд в своих еретических верованиях). Каждого еретика можно победить в бою, затратив `S` силы, и он исчезнет. А если потратить `V` силы, то еретик раскается в своих заблуждениях и сразу перейдет на сторону Инквизиции (тем самым, увеличив силу отряда инквизиторов на `S`). Еретиков можно побеждать или обращать на свою сторону последовательно, одного за другим, в произвольном порядке. Определите минимальную начальную силу отряда инквизиции, достаточную для полной ликвидации всей группы еретиков.
В первой строке ввода содержится единственное натуральное число `N` (`1<=N<=100`) - число еретиков.
Затем следует `N` строк - описаний еретиков. В каждой строке вводятся два натуральных числа `S` и `V` (`1<=S,V<=100`) - сила и убежденность каждого еретика соответственно.
В первой строке выведите единственное натуральное число `X` - минимальную стартовую силу отряда.
Затем выведите `N` строк - пошаговый план борьбы с еретиками. В каждой строке указывается номер еретика (от 1 до `N`), устраняемого на соответствующем шаге, и число 0 или 1: 0, если еретик должен быть побежден, или 1, если он должен быть обращен.
```sample Пример ввода
3
6 2
6 20
4 1
```
```sample Пример вывода
1
3 1
1 1
2 0
```
Пояснение: потратив всю стартовую силу 1, мы обращаем 3-го еретика, и отряд теперь имеет силу 4; затем обращаем 1-го еретика за 2, и отряд теперь имеет силу 4-2+6=8; наконец, побеждаем 2-го еретика в бою - у нас достаточно сил для этого.
Начало
Рабочее место участника
Динамическое программирование и запоминающие функции