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

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

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

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

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

В первой строке находятся два целых числа NN и SS(11 \le NN \le 200000200000, 00 \le SS \le 10910^9) — количество дней и изначальное количество денег.

В следующих NN строках находятся по два целых числа aia_i и bib_i(00 \le aia_i,bib_i \le 10910^9).

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

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

Примеры

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

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