Canada Cup 2016 |
---|
Закончено |
Одной из традиций соревнований ACM-ICPC является раздача командам воздушных шариков за каждую сданную задачу. В данной задаче мы считаем, что штрафное время не имеет значения, и команды упорядочиваются только по количеству воздушных шариков. Это означает, что место команды равно количеству команд со строго большим количеством шариков, увеличенное на 1. Например, если семь команд имеют больше шариков, то ваша команда займёт восьмое место. Разрешается, чтобы несколько команд занимали одно и то же место.
Вам следует знать, что перед соревнованием полезно плотно кушать. Если количество шариков у команды превышает суммарный вес её участников, то команда начинает летать по площадке и случайно касается потолка, что строго запрещено правилами и приводит к немедленной дисквалификации команды. Дисквалифицированные команды не учитываются в результатах.
Соревнование только что завершилось. Всего участвовали n команд, пронумерованных от 1 до n. Команда с номером i заработала ti шариков и имеет суммарный вес wi. Гарантируется, что ti не превосходит wi, то есть изначально ни одна команда не летает.
Лимак выступает за первую команду. Он не любит читерство, поэтому никогда не заберёт шарик у другой команды. Вместо этого он может отдавать шарики своей команды другим командам, добившись с помощью этого, чтобы они летали и были дисквалифицированы. Лимак может раздать любое количество шариков от нуля до количества шариков у его команды.
Какое самое лучше (минимальное) место может занять в итоге команда Лимака?
В первой строке входных данных записано число n (2 ≤ n ≤ 300 000) — количество команд.
В i-й из последующих n строк записаны два целых числа ti и wi (0 ≤ ti ≤ wi ≤ 1018) — количество шариков и вес i-й команды соответственно. Лимак является участником из первой команды.
Выведите одно целое число — лучшее место, которое может занять Лимак.
8
20 1000
32 37
40 1000
45 50
16 16
16 16
14 1000
2 1000
3
7
4 4
4 4
4 4
4 4
4 4
4 4
5 5
2
7
14000000003 1000000000000000000
81000000000 88000000000
5000000000 7000000000
15000000000 39000000000
46000000000 51000000000
0 1000000000
0 0
2
В первом примере у Лимака вначале есть 20 шариков. У трёх команд больше шариков (32, 40 и 45 шариков), поэтому Лимак занимает изначально четвёртое место. Одной из оптимальных стратегий является:
Во втором примере Лимак занимает второе место и никак не может его улучшить.
В третьем примере у Лимака достаточно шариков, чтобы избавиться от команд 2, 3 и 5 (то есть команд с 81 000 000 000, 5 000 000 000 и 46 000 000 000 шариками соответственно). У Лимака остаётся 0 шариков, и он занимает второе место (разделив его с командами 6 и 7).
Название |
---|