Задача B. Свечи

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:64 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

Девочка Вика любит в новогоднюю ночь зажигать свечи. Вот и в этот раз она зажгла n свечей. Каждая свеча характеризуется двумя параметрами: высотой (в сантиметрах) и скоростью сгорания (в сантиметрах в минуту). Помогите Вике определить, через какое целое число минут погаснет не менее половины всех зажженных свечек?

Формат входных данных

Первая строка входного файла содержит натуральное число n — количество зажженных свечек. Во второй строке через пробел расположены n целых чисел xi — высота i-й свечки. В третьей строке через пробел расположены n целых чисел yi — скорость сгорания i-й свечки.

Формат выходных данных

Выведите одно натуральное число — количество минут, необходимые для того, чтобы сгорело и погасло не менее половины всех свечек.

Ограничения

1 ≤ n ≤ 105

1 ≤ xi, yi ≤ 109

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие при n = 1, получат не менее 10 баллов.

Решения, верно работающие при n = 2, получат не менее 20 баллов.

Пояснение к примеру

В примере дано три свечи высотой 20, 6 и 12 сантиметров. Первая свеча сгорает со скоростью 1 см/мин, следовательно она будет гореть ровно 20 минут. Вторая свеча сгорает со скоростью 5 см/мин, следовательно она будет гореть 65 = 115 минут. Третья свеча сгорает со скоростью 7 см/мин, следовательно она будет гореть 127 = 157 минут. Таким образом уже через две минуты погаснут две свечи из трех.

Примеры тестов

Стандартный вход Стандартный выход
1
3
20 6 12
1 5 7
2

0.220s 0.035s 15