D. Шарики на контесте
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Одной из традиций соревнований 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 шариков), поэтому Лимак занимает изначально четвёртое место. Одной из оптимальных стратегий является:

  1. Лимак отдаёт 6 шариков команде с 32 шариками и весом 37. Этого как раз достаточно, чтобы эта команда начала летать. К сожалению, теперь у Лимака только 14 шариков, и его команда опускается на пятое место.
  2. Лимак отдаёт 6 шариков команде с 45 шариками. Теперь у них 51 шарик при весе 50, и они также зарабатывают дисквалификацию.
  3. Лимак отдаёт по 1 шарику каждой из двух команд с 16 шариками.
  4. Теперь у Лимака 20 - 6 - 6 - 1 - 1 = 6 шариков.
  5. Осталось три команды, у которых 40, 14 и 2 шарика.
  6. Команда Лимака занимает третье место, потому что у двух команд строго больше шариков.

Во втором примере Лимак занимает второе место и никак не может его улучшить.

В третьем примере у Лимака достаточно шариков, чтобы избавиться от команд 2, 3 и 5 (то есть команд с 81 000 000 000, 5 000 000 000 и 46 000 000 000 шариками соответственно). У Лимака остаётся 0 шариков, и он занимает второе место (разделив его с командами 6 и 7).