Сервер олимпиад

Ставропольский государственный университет

Имя
Пароль

Server Off-Line
Server time: 11 Dec 2024 22:13:34

Банк задач


Номер задачи - 2

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

Ограничение - 1 сек. на один тест

Летним днем группа из N школьников гуляла в лесу. Они набрели на большую и довольно глубокую яму и как ни странно, все они, один за другим, упали в эту яму.

Глубина ямы равна H. Каждый знает свой рост hi и длину своих рук li. Таким образом, если i-ый школьник поднимет руки, то его ладони окажутся на высоте hi + li от уровня дна ямы. Кроме того, школьники могут, вставая друг другу на плечи, образовывать вертикальную колонну. Если под школьником i стоят ребята j1, j2, :, jk, то он может дотянуться до уровня hj1 + hj2 + : + hjk + hi + li.

Если школьник может дотянуться до края ямы, он может выбраться. Выбравшиеся ребята никак не могут помогать оставшимся в яме.

Ребята не стали унывать и решили определить какое наибольшее количество людей может выбраться из ямы до прибытия группы спасателей.

Определите наибольшее количество школьников, которые смогут выбраться до прибытия спасателей.

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

В первой строке входного файла записано натуральное число N (1 ≤ N ≤ 2000) - количество ребят попавших в яму.

Далее в N строках указан их рост hi (1 ≤ hi ≤ 104) и длина рук li (1 ≤ li 104). Рост и длина рук - целые числа.

В последней строке указана глубина ямы H (1 ≤ H ≤ 104)$

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

Выведите K - максимальное количество людей, которые смогут выбраться из ямы. Во второй строке выведите номера людей, которые смогут выбраться. Люди нумеруются с единицы в том порядке, в котором они заданы во входном файле.

Примеры
stdin stdout
2
10 5
5 2
20
1
1
Rambler's Top100 | Карта сайта | Контакты | Copyright © 2005-2007, Ставропольский государственный университет.