Областная олимпиада по информатике 2022 года за 11 класс | Казахстанские олимпиады

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

У Ади есть $S$ тенге. В каждый из следующих $N$ дней он решил, что будет либо целый день работать, либо целый день отдыхать. Он высчитал, что если будет работать в i-й день, то заработает $a_i$ тенге. А чтобы отдохнуть в i-й день, он потратит $b_i$ тенге. Другими словами, если в i-й день он будет работать, то количество его денег увеличиться на $a_i$, а если будет отдыхать, то количество денег уменьшится на $b_i$. Какое максимальное количество дней он может отдохнуть? При этом, ни в какой момент времени количество его денег не должно быть отрицательным.

Формат входного файла

В первой строке находятся два целых числа $N$ и $S$($1$ $\le$ $N$ $\le$ $200000$, $0$ $\le$ $S$ $\le$ $10^9$) — количество дней и изначальное количество денег.

В следующих $N$ строках находятся по два целых числа $a_i$ и $b_i$($0$ $\le$ $a_i$,$b_i$ $\le$ $10^9$).

Формат выходного файла

Выведите одно целое число — максимальное количество дней, в которые Ади может отдохнуть.

Примеры

Входные данные

Выходные данные