Codeforces Round 751 (Div. 1) |
---|
Закончено |
Группа из $$$n$$$ альпинистов подошла к подножию горы. Сложность подъема на эту гору можно оценить целым числом $$$d$$$.
Каждого альпиниста можно описать всего двумя целыми числами $$$s$$$ и $$$a$$$, где $$$s$$$ характеризует навык альпиниста по восхождению на горы, а $$$a$$$ характеризует его аккуратность.
Альпинист с навыком $$$s$$$ может забраться на гору сложности $$$p$$$ только в том случае, если $$$p \leq s$$$. Во время того, как он забирается, он немного меняет путь, по которому идёт, а вместе с ним и его сложность. А именно, после того как на гору сложности $$$p$$$ забирается альпинист с аккуратностью $$$a$$$, сложность горы становится равной $$$\max(p, a)$$$.
Альпинисты решили подниматься на гору по одному. Но сначала всем стало интересно, какое максимальное количество альпинистов смогут забраться на эту гору, если они будут залезать в оптимальном порядке. А так как в группе только вы увлекаетесь программированием, отвечать на этот вопрос придется вам.
Заметим, что после того, как порядок выбран, каждый альпинист, который может подняться на гору, должен подняться в отведенный ему момент.
В первой строке заданы два целых числа $$$n$$$ и $$$d$$$ ($$$1 \leq n \leq 500\,000$$$; $$$0 \leq d \leq 10^9$$$) — количество альпинистов в группе и изначальная сложность горы.
В каждой из последующих $$$n$$$ строк содержится по два целых числа $$$s_i$$$ и $$$a_i$$$ ($$$0 \leq s_i, a_i \leq 10^9$$$) — навык восхождению на горы $$$i$$$-го альпиниста и его аккуратность.
Выведите одно число — максимальное количество альпинистов, которые смогут забраться на гору, если они будут подниматься на неё в оптимальном порядке.
3 2 2 6 3 5 5 7
2
3 3 2 4 6 4 4 6
2
5 0 1 5 4 8 2 7 7 6 3 2
3
В первом примере из условия на гору могут забраться альпинисты $$$2$$$ и $$$3$$$ в таком порядке. Других вариантов, при которых забираются $$$2$$$ альпиниста, нет.
Во втором примере из условия альпинист $$$1$$$ забраться не может, потому что изначальная сложность горы слишком велика, а альпинисты $$$2$$$ и $$$3$$$ могут забраться в любом порядке.
В третьем примере из условия на гору взберутся альпинисты $$$5$$$, $$$3$$$ и $$$4$$$, причём именно в таком порядке, других вариантов нет.
Название |
---|