Одной из традиций соревнований ACM-ICPC является раздача командам воздушных шариков за каждую сданную задачу. В данной задаче мы считаем, что штрафное время не имеет значения, и команды упорядочиваются только по количеству воздушных шариков. Это означает, что место команды равно количеству команд со строго большим количеством шариков, увеличенное на 1. Например, если семь команд имеют больше шариков, то ваша команда займёт восьмое место. Разрешается, чтобы несколько команд занимали одно и то же место.
Вам следует знать, что перед соревнованием полезно плотно кушать. Если количество шариков у команды превышает суммарный вес её участников, то команда начинает летать по площадке и случайно касается потолка, что строго запрещено правилами и приводит к немедленной дисквалификации команды. Дисквалифицированные команды не учитываются в результатах.
Соревнование только что завершилось. Всего участвовали n команд, пронумерованных от 1 до n. Команда с номером i заработала ti шариков и имеет суммарный вес wi. Гарантируется, что ti не превосходит wi, то есть изначально ни одна команда не летает.
Лимак выступает за первую команду. Он не любит читерство, поэтому никогда не заберёт шарик у другой команды. Вместо этого он может отдавать шарики своей команды другим командам, добившись с помощью этого, чтобы они летали и были дисквалифицированы. Лимак может раздать любое количество шариков от нуля до количества шариков у его команды.
Какое самое лучше (минимальное) место может занять в итоге команда Лимака?
Примечание
В первом примере у Лимака вначале есть 20 шариков. У трёх команд больше шариков (32, 40 и 45 шариков), поэтому Лимак занимает изначально четвёртое место. Одной из оптимальных стратегий является:
- Лимак отдаёт 6 шариков команде с 32 шариками и весом 37. Этого как раз достаточно, чтобы эта команда начала летать. К сожалению, теперь у Лимака только 14 шариков, и его команда опускается на пятое место.
- Лимак отдаёт 6 шариков команде с 45 шариками. Теперь у них 51 шарик при весе 50, и они также зарабатывают дисквалификацию.
- Лимак отдаёт по 1 шарику каждой из двух команд с 16 шариками.
- Теперь у Лимака 20 - 6 - 6 - 1 - 1 = 6 шариков.
- Осталось три команды, у которых 40, 14 и 2 шарика.
- Команда Лимака занимает третье место, потому что у двух команд строго больше шариков.
Во втором примере Лимак занимает второе место и никак не может его улучшить.
В третьем примере у Лимака достаточно шариков, чтобы избавиться от команд 2, 3 и 5 (то есть команд с 81 000 000 000, 5 000 000 000 и 46 000 000 000 шариками соответственно). У Лимака остаётся 0 шариков, и он занимает второе место (разделив его с командами 6 и 7).