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

Условие

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

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

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

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

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

Ограничения

1 ≤ n ≤ 10⁵

1 ≤ x_i, y_i ≤ 10⁹

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

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

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

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

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

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

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

3
20 6 12
1 5 7

2