EduBrick

M. Планирование с дедлайнами

3000 мс · 256 МБ · всё или ничего

Дано nn работ; работа ii занимает tit_i единиц времени и должна быть закончена не позже момента did_i. Работы выполняются последовательно, начиная с момента 0, в любом порядке; прерывать работу нельзя. Сколько работ можно успеть?

Формат ввода

В первой строке - число nn (1≤n≤2⋅1051 \le n \le 2 \cdot 10^5).

В следующих nn строках - пары tit_i и did_i (1≤ti,di≤1091 \le t_i, d_i \le 10^9).

Формат вывода

Одно число - наибольшее количество работ, которые можно успеть.

Примеры

ввод
3
2 3
1 2
5 6
вывод
2
ввод
1
5 3
вывод
0
Разбор идеи от автора задачи. Сначала попробуйте сами.
Войдите, чтобы отправлять решения.