3-й этап Республиканской олимпиады по информатике 2021-2022, 2 тура


Задача A. Работать или отдыхать?

Ограничение по времени:
1.5 секунд
Ограничение по памяти:
256 мегабайт

У Ади есть $S$ тенге. В каждый из следующих $N$ дней он решил, что будет либо целый день работать, либо целый день отдыхать. Он высчитал, что если будет работать в $i$-й день, то заработает $a_i$ тенге. А чтобы отдохнуть в $i$-й день, он потратит $b_i$ тенге. Другими словами, если в $i$-й день он будет работать, то количество его денег увеличиться на $a_i$, а если будет отдыхать, то количество денег уменьшится на $b_i$. Какое максимальное количество дней он может отдохнуть? При этом, ни в какой момент времени количество его денег не должно быть отрицательным.
Формат входного файла
В первой строке находятся два целых числа $N$ и $S$($1 <= N <= 200000$, $0 <= S <= 10^9$) — количество дней и изначальное количество денег. В следующих $N$ строках находятся по два целых числа $a_i$ и $b_i(0 <= a_i,b_i <= 10^9)$.
Формат выходного файла
Выведите одно целое число — максимальное количество дней, в которые Ади может отдохнуть.
Примеры:
Вход
3 5
1 4
1 3
2 3
Ответ
2
Вход
5 12
0 5
0 4
0 7
0 4
0 4
Ответ
3
Замечание
В первом примере: в первый день он будет работать, а второй и третий день отдыхать. Во втором примере: он будет отдыхать в дни $2$, $4$ и $5$. ( Temirlan Satylkhanov )
посмотреть в олимпиаде

Комментарий/решение:

  0
2023-02-09 15:47:31.0 #

Как я понял это задача о ранце с динамической грузоподъемностью, если нет пожалуйста можете дать подсказку

  0
2023-02-13 10:43:30.0 #

показать/скрыть код

легчайшая