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

Условие

Теплым весенним днем группа из N школьников-программистов гуляла в окрестностях города Кисловодска. К несчастью, они набрели на большую и довольно глубокую яму. Как это случилось — непонятно, но вся компания оказалась в этой яме.

Глубина ямы равна H. Каждый школьник знает свой рост по плечи h_i и длину своих рук l_i. Таким образом, если он, стоя на дне ямы, поднимет руки, то его ладони окажутся на высоте h_i + l_i от уровня дна ямы. Школьники могут, вставая друг другу на плечи, образовывать вертикальную колонну. При этом любой школьник может встать на плечи любого другого школьника. Если под школьником i стоят школьники j₁, j₂, …, j_k, то он может дотянуться до уровня h_j1 + h_j2 + …  + h_jk + h_i + l_i.

Если школьник может дотянуться до края ямы (то есть h_j1 + h_j2 + …  + h_jk + h_i + l_i ≥ H), то он может выбраться из нее. Выбравшиеся из ямы школьники не могут помочь оставшимся.

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

Решение, дающее правильный ответ только при N ≤ 100; H, h_i, l_i ≤ 1000, будет оцениваться из 70 баллов.

Формат входного файла

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

Далее в N строках указаны по два целых числа: рост i-го школьника по плечи h_i (1 ≤ hi ≤ 10⁵) и длина его рук l_i (1 ≤ l_i ≤ 10⁵).

В последней строке указано целое число — глубина ямы H (1 ≤ H ≤ 10⁵).

Формат выходного файла

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

Примеры тестов

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