Пицца для вечеринки
시간 제한2초메모리 제한1024 MB
N개의 피자를 한 대의 전자레인지로 순서대로 데울 때, i번째 피자는 ai초 동안 데운 뒤 bi초 동안 뜨거운 상태를 유지한다. 어느 한 순간에 동시에 뜨거운 피자의 최대 개수를 구한다.
문제
Еще только начался март, а студент первого курса НУОП (Неизвестного университета олимпиадного программирования) Вениамин уже закрыл сессию — чем не повод устроить вечеринку?
Вениамин назначил день и час, пригласил всех своих друзей и заказал огромное количество пиццы. Он выбирал какую-нибудь новую настольную игру, которую никто из его друзей еще не видел, когда произошло неприятное событие — пиццу доставили гораздо раньше, чем планировалось. Так как к приходу друзей пицца уже гарантированно остынет, необходимо заранее продумать организацию процесса ее разогрева. Теория расписаний изучается в НУОП только на третьем курсе, так что Вениамин обращается к вам за помощью, разумеется, предварительно строго сформулировав задачу:
-
Всего у Вениамина имеется N пицц.
-
Его цель — выбрать такой порядок разогревания пицц в микроволновке, чтобы в некоторый момент времени как можно больше пицц оказались горячими.
-
Каждая пицца характеризуется ровно двумя параметрами ai и bi:
- ai обозначает время в секундах, необходимое для разогрева i-й пиццы в микроволновой печи;
- bi обозначает время в секундах, в течение которого пицца остается горячей.
-
Для разогревания пицц можно использовать только микроволновку, которая у Вениамина ровно одна. Чтобы пицца стала горячей, она должна находится в микроволновке непрерывный отрезок времени длительностью ровно ai секунд.
-
В каждый момент времени в микроволновке может находиться не более одной пиццы.
-
Можно считать, что все действия по управлению микроволновкой Веня совершает мгновенно (включить или выключить микроволновку, достать или убрать пиццу).
-
Также можно считать, что поедание пицц происходит моментально. Иными словами, нужно добиться того, чтобы максимальное количество пицц было горячими в какойто момент времени, не обязательно в некий промежуток ненулевой длины.
입력
В первой строке входных данных записано целое число N — количество пицц (1 ≤ N ≤ 300 000). Следующие N строк содержат описания пицц, каждое из которых состоит из двух целых чисел ai и bi (1 ≤ ai, bi ≤ 109).
출력
Выведите единственное число — максимальное количество пицц, которые могут одновременно оказаться горячими.
힌트
Разберем подробнее первый тест из условия:
- В нулевой момент времени Вениамин убирает в микроволновку первую пиццу.
- В момент времени 1 Вениамин достает из микроволновки первую пиццу и кладет туда вторую.
- В момент времени 2 Веня достает из микроволновки вторую пиццу, в этот момент первая пицца еще горячая, следовательно, ответ на задачу — 2. Обратите внимание, что две пиццы будут горячими только в этот момент времени, и добиться того, чтобы они были горячими в течение ненулевого по длине промежутка времени, в данном примере невозможно.