30840번 - Пицца для вечеринки 다국어

문제

Еще только начался март, а студент первого курса НУОП (Неизвестного университета олимпиадного программирования) Вениамин уже закрыл сессию — чем не повод устроить вечеринку?

Вениамин назначил день и час, пригласил всех своих друзей и заказал огромное количество пиццы. Он выбирал какую-нибудь новую настольную игру, которую никто из его друзей еще не видел, когда произошло неприятное событие — пиццу доставили гораздо раньше, чем планировалось. Так как к приходу друзей пицца уже гарантированно остынет, необходимо заранее продумать организацию процесса ее разогрева. Теория расписаний изучается в НУОП только на третьем курсе, так что Вениамин обращается к вам за помощью, разумеется, предварительно строго сформулировав задачу:

• Всего у Вениамина имеется N пицц.
• Его цель — выбрать такой порядок разогревания пицц в микроволновке, чтобы в некоторый момент времени как можно больше пицц оказались горячими.
• Каждая пицца характеризуется ровно двумя параметрами a_i и b_i:
  • a_i обозначает время в секундах, необходимое для разогрева i-й пиццы в микроволновой печи;
  • b_i обозначает время в секундах, в течение которого пицца остается горячей.
• Для разогревания пицц можно использовать только микроволновку, которая у Вениамина ровно одна. Чтобы пицца стала горячей, она должна находится в микроволновке непрерывный отрезок времени длительностью ровно ai секунд.
• В каждый момент времени в микроволновке может находиться не более одной пиццы.
• Можно считать, что все действия по управлению микроволновкой Веня совершает мгновенно (включить или выключить микроволновку, достать или убрать пиццу).
• Также можно считать, что поедание пицц происходит моментально. Иными словами, нужно добиться того, чтобы максимальное количество пицц было горячими в какойто момент времени, не обязательно в некий промежуток ненулевой длины.

입력

В первой строке входных данных записано целое число N — количество пицц (1 ≤ N ≤ 300 000). Следующие N строк содержат описания пицц, каждое из которых состоит из двух целых чисел a_i и b_i (1 ≤ a_i, b_i ≤ 10⁹).

출력

Выведите единственное число — максимальное количество пицц, которые могут одновременно оказаться горячими.

제한

노트

Разберем подробнее первый тест из условия:

• В нулевой момент времени Вениамин убирает в микроволновку первую пиццу.
• В момент времени 1 Вениамин достает из микроволновки первую пиццу и кладет туда вторую.
• В момент времени 2 Веня достает из микроволновки вторую пиццу, в этот момент первая пицца еще горячая, следовательно, ответ на задачу — 2. Обратите внимание, что две пиццы будут горячими только в этот момент времени, и добиться того, чтобы они были горячими в течение ненулевого по длине промежутка времени, в данном примере невозможно.