Задача №113190. Приключение
Теплым весенним днем группа из \(N\) школьников-программистов гуляла в окрестностях города Кисловодска. К несчастью, они набрели на большую и довольно глубокую яму. Как это случилось — непонятно, но вся компания оказалась в этой яме.
Глубина ямы равна \(H\). Каждый школьник знает свой рост по плечи \(h_i\) и длину своих рук \(l_i\). Таким образом, если он, стоя на дне ямы, поднимет руки, то его ладони окажутся на высоте \(h_i + l_i\) от уровня дна ямы. Школьники могут, вставая друг другу на плечи, образовывать вертикальную колонну. При этом любой школьник может встать на плечи любого другого школьника. Если под школьником \(i\) стоят школьники \(j_1, j_2, \ldots, j_k\), то он может дотянуться до уровня \(h_{j1} + h_{j2} + \ldots + h_{jk} + h_i + l_i\).
Если школьник может дотянуться до края ямы (то есть \(h_{j1} + h_{j2} + \ldots + h_{jk} + h_i + l_i \geq H\)), то он может выбраться из нее. Выбравшиеся из ямы школьники не могут помочь оставшимся.
Найдите наибольшее количество школьников, которые смогут выбраться из ямы до прибытия помощи, и перечислите их номера.
В первой строке входного файла записано натуральное число \(N\) — количество школьников, попавших в яму.
Далее в \(N\) строках указаны по два целых числа: рост \(i\)-го школьника по плечи \(h_i\) и длина его рук \(l_i\).
В последней строке указано целое число — глубина ямы \(H\).
В первой строке выведите \(K\) — максимальное количество школьников, которые смогут выбраться из ямы. Если \(K > 0\), то во второй строке выведите их номера в том порядке, в котором они вылезают из ямы. Школьники нумеруются с единицы в том порядке, в котором они заданы во входном файле. Если существует несколько решений, выведите любое.
Подзадача 1 (30 баллов) \(n \le 2\,000\) и \(1 \le l_i, h_i, H \le 1\,000\)
Подзадача 2 (40 баллов) \(n \le 2\,000\) и \(1 \le l_i, h_i, H \le 10^5\)
Подзадача 3 (30 баллов) \(n \le 100\,000\) и \(1 \le l_i, h_i, H \le 10^9\)
2 10 4 5 2 20
0
6 6 7 3 1 8 5 8 5 4 2 10 5 30
4 2 5 1 3