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
)
Комментарий/решение:
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.