Пицца для вечеринки

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

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

• Всего у Вениамина имеется N пицц.

• Его цель — выбрать такой порядок разогревания пицц в микроволновке, чтобы в некоторый момент времени как можно больше пицц оказались горячими.

• Каждая пицца характеризуется ровно двумя параметрами ai и bi:

  • ai обозначает время в секундах, необходимое для разогрева i-й пиццы в микроволновой печи;
  • bi обозначает время в секундах, в течение которого пицца остается горячей.

• Для разогревания пицц можно использовать только микроволновку, которая у Вениамина ровно одна. Чтобы пицца стала горячей, она должна находится в микроволновке непрерывный отрезок времени длительностью ровно ai секунд.

• В каждый момент времени в микроволновке может находиться не более одной пиццы.

• Можно считать, что все действия по управлению микроволновкой Веня совершает мгновенно (включить или выключить микроволновку, достать или убрать пиццу).

• Также можно считать, что поедание пицц происходит моментально. Иными словами, нужно добиться того, чтобы максимальное количество пицц было горячими в какойто момент времени, не обязательно в некий промежуток ненулевой длины.

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

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

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

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