XVIII всероссийская олимпиада школьников по информатике в Кисловодске.

Назад

Задача 3.Приключение

Имя входного файла: advent.in
Имя выходного файла: advent.out
Максимальное время работы на одном тесте: 2 секунды
Максимальный объем используемой памяти: 64 мегабайта
Максимальная оценка: 100 баллов

       Теплым весенним днем группа из N школьников-программистов гуляла в окрестностях города Кисловодска. К несчастью, они набрели на большую и довольно глубокую яму. Как это случилось — непонятно, но вся компания оказалась в этой яме.
       Глубина ямы равна H. Каждый школьник знает свой рост по плечи hi и длину своих рук li. Таким образом, если он, стоя на дне ямы, поднимет руки, то его ладони окажутся на высоте hi + li от уровня дна ямы. Школьники могут, вставая друг другу на плечи, образовывать вертикальную колонну. При этом любой школьник может встать на плечи любого другого школьника. Если под школьником i стоят школьники j1, j2, …, jk, то он может дотянуться до уровня hj1 + hj2 + … + hjk + hi + li.
       Если школьник может дотянуться до края ямы (то есть hj1 + hj2 + … + hjk + hi + li >= H), то он может выбраться из нее. Выбравшиеся из ямы школьники не могут помочь оставшимся.
       Найдите наибольшее количество школьников, которые смогут выбраться из ямы до прибытия помощи, и перечислите их номера.

Формат входных данных

       В первой строке входного файла записано натуральное число N (1 <= N <= 2000) — количество школьников, попавших в яму.
       Далее в N строках указаны по два целых числа: рост i-го школьника по плечи hi (1 <= hi <= 105) и длина его рук li (1 <= li <= 105).
       В последней строке указано целое число — глубина ямы H (1 <= H <= 105).

Формат выходных данных

       В первой строке выведите K — максимальное количество школьников, которые смогут выбраться из ямы. Если K > 0, то во второй строке в произвольном порядке выведите их номера, разделяя их пробелами. Школьники нумеруются с единицы в том порядке, в котором они заданы во входном файле. Если существует несколько решений, выведите любое.

Примеры:

advent.in advent.out
2
10 4
5 2
20 		0
6
6 7
3 1
8 5
8 5
4 2
10 5
30 		4
1 4 2 5

Примеры:

       Решение, дающее правильный ответ только при N <= 100; H, hi, li <= 1000, будет оцениваться из 70 баллов.
Личный сайт им. РОССОМАХи ICQ: 229654802 e-mail: poc.leb@mail.ru design by: POCCOMAXA
Сайт создан в системе uCoz