Теплым весенним днем группа из
N школьников-программистов гуляла в окрестностях города Кисловодска. К несчастью, они набрели на большую и довольно глубокую яму. Как это случилось — непонятно, но вся компания оказалась в этой яме.
Глубина ямы равна
H. Каждый школьник знает свой рост по плечи h
i и длину своих рук l
i. Таким образом, если он, стоя на дне ямы, поднимет руки, то его ладони окажутся на высоте h
i + l
i от уровня дна ямы. Школьники могут, вставая друг другу на плечи, образовывать вертикальную колонну. При этом любой школьник может встать на плечи любого другого школьника. Если под школьником i стоят школьники j
1, j
2, …, j
k, то он может дотянуться до уровня h
j1 + h
j2 + … + h
jk + h
i + l
i.
Если школьник может дотянуться до края ямы (то есть h
j1 + h
j2 + … + h
jk + h
i + l
i ≥ H), то он может выбраться из нее. Выбравшиеся из ямы школьники не могут помочь оставшимся.
Найдите наибольшее количество школьников, которые смогут выбраться из ямы до прибытия помощи, и перечислите их номера.
Формат входных данных
В первой строке входных данных задается натуральное число
N (1 ≤
N ≤ 2000) — количество школьников, попавших в яму.
Далее в
N строках содержится по два целых числа: рост i-го школьника по плечи h
i (1 ≤ h
i ≤ 10
5) и длина его рук l
i (1 ≤ l
i ≤ 10
5).
В последней строке указано целое число — глубина ямы
H (1 ≤
H ≤ 10
5).
Формат выходных данных
В первой строке выведите
K — максимальное количество школьников, которые смогут выбраться из ямы. Если
K > 0, то во второй строке в произвольном порядке выведите их номера, разделяя их пробелами. Школьники нумеруются с единицы в том порядке, в котором они заданы во входных данных. Если существует несколько решений, выведите любое.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1
239 239
566
|
0
|
|
2
|
3
1 2
1 2
4 1
7
|
2
2 1
|