Задача №112096. Пицца для вечеринки
Еще только начался март, а студент первого курса НУОП (Неизвестного университета олимпиадного программирования) Вениамин уже закрыл сессию — чем не повод устроить вечеринку?
Вениамин назначил день и час, пригласил всех своих друзей и заказал огромное количество пиццы. Он выбирал какую-нибудь новую настольную игру, которую никто из его друзей еще не видел, когда произошло неприятное событие — пиццу доставили гораздо раньше, чем планировалось. Так как к приходу друзей пицца уже гарантированно остынет, необходимо заранее продумать организацию процесса ее разогрева. Теория расписаний изучается в НУОП только на третьем курсе, так что Вениамин обращается к вам за помощью, разумеется, предварительно строго сформулировав задачу:
* Всего у Вениамина имеется N пицц.
* Его цель — выбрать такой порядок разогревания пицц в микроволновке, чтобы в некоторый момент времени как можно больше пицц оказались горячими.
Каждая пицца характеризуется ровно двумя параметрами \(a_i\) и \(b_i\):
– \(a_i\) обозначает время в секундах, необходимое для разогрева \(i\)-й пиццы в микро- волновой печи;
– \(b_i\) обозначает время в секундах, в течение которого пицца остается горячей
* Для разогревания пицц можно использовать только микроволновку, которая у Вениамина ровно одна. Чтобы пицца стала горячей, она должна находится в микроволновке непрерывный отрезок времени длительностью ровно \(a_i\) секунд.
* В каждый момент времени в микроволновке может находиться не более одной пиццы
* Можно считать, что все действия по управлению микроволновкой Веня совершает мгновенно (включить или выключить микроволновку, достать или убрать пиццу).
* Также можно считать, что поедание пицц происходит моментально. Иными словами, нужно добиться того, чтобы максимальное количество пицц было горячими в какой- то момент времени, не обязательно в некий промежуток ненулевой длины.
В первой строке входных данных записано целое число \(N\) — количество пицц (1 ≤ \(N\) ≤ 300 000). Следующие \(N\) строк содержат описания пицц, каждое из которых состоит из двух целых чисел \(a_i\) и \(b_i\) (1 ≤ \(a_i\); \(b_i\) ≤ \(10^{9}\)).
Выведите единственное число — максимальное количество пицц, которые могут одновременно оказаться горячими
Разберем подробнее первый тест из условия:
* В нулевой момент времени Вениамин убирает в микроволновку первую пиццу.
* В момент времени 1 Вениамин достает из микроволновки первую пиццу и кладет туда вторую.
* В момент времени 2 Веня достает из микроволновки вторую пиццу, в этот момент первая пицца еще горячая, следовательно, ответ на задачу — 2. Обратите внимание, что две пиццы будут горячими только в этот момент времени, и добиться того, чтобы они были горячими в течение ненулевого по длине промежутка времени, в данном примере невозможно.
Тесты к этой задаче состоят из пяти групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов предыдущих групп.
0. Тесты 1–2. Тесты из условия, оцениваются в ноль баллов.
1. Тесты 3–15. В тестах этой группы \(N\) ≤ 10. Эта группа оценивается в 20 баллов.
2. Тесты 16–30. В тестах этой группы \(N\) ≤ 20. Эта группа оценивается в 20 баллов.
3. Тесты 31–45. В тестах этой группы \(N\) ≤ 5 000. Эта группа оценивается в 20 баллов.
4. В тестах этой группы дополнительные ограничения отсутствуют. Эта группа оценивается в 40 баллов.
2 1 1 1 1
2
4 2 12 10 8 7 5 5 1
3