eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Пригода

Пригода

Теплого весняного дня група з \textbf{N} школярів-програмістів гуляла в околицях міста Кисловодська. На нещастя, вони набрели на велику і достатньно глибоку яму. Як це трапилось --- незрозуміло, але уся компанія опинилась у цій ямі. Глибина ями рівна \textbf{H}. Кожен школяр знає свій зріст до плечей \textbf{h_i} та довину своїх рук \textbf{l_i}. Таким чином, якщо він, стоячи на дні ями, підніме руки, то його долоні опиняться на висоті \textbf{h_i + l_i} від рівня дна ями. Школярі можуть, стаючи один одному на плечі, утворювати вертикальну колону. При цьому довільний школяр може стати на плечі довільного іншого школяра. Якщо під школярем \textbf{i} стоять школярі \textbf{j_1}, \textbf{j_2}, ..., \textbf{j_k}, то він може дотягнутись до рівня \textbf{h_j1 + h_j2 + ... + h_jk + h_i + l_i}. Якщо школяр може дотягнутись до краю ями (тобто \textbf{h_j1 + h_j2 + ... + h_jk + h_i + l_i} ≤ \textbf{H}), то він може вибратись з неї. Школярі, що вибрались з ями, не можуть дпомогтитим, що в ній залишились. Знайдіть найбільшу кількість школярів, які зможуть вибратись з ями до прибуття допомоги, і перерахутйе їхні номери. \InputFile У першому рядку вхідного файлу записано натуральне число \textbf{N} (\textbf{N} ≤ \textbf{100000}) --- кількість школярів, які потрапили до ями. Далі у \textbf{N} рядках вказано по два цілих числа: зріст \textbf{i}-го школяра по плечі \textbf{h_i} та довжина його рук \textbf{l_i} (\textbf{1} ≤ \textbf{l_i}, \textbf{h_i} ≤ \textbf{10^9}). У останньому рядку вказано ціле число --- глибина ями \textbf{H} (\textbf{1} ≤ \textbf{H} ≤ \textbf{10^9}). \OutputFile У першому рядку виведіть \textbf{K} --- максимальну кількість школярів, які зможуть вибратись з ями. Якщо \textbf{K} >\textbf{0}, то у другому рядку у довільному порядку виведіть їхні номери, відокремлюючи їх пропусками. Школярі нумеруються від одиниці у тому порядку, у якому вони задані у вхідному файлі. Якщо існує декілька розв'язків, виведіть довільний.
Ліміт часу 0.5 секунд
Ліміт використання пам'яті 256 MiB
Вхідні дані #1
2
10 4
5 2
20
Вихідні дані #1
0