D. Вычислительная мощность
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам необходимо выполнить некоторое количество задач, для каждой задачи известно, сколько процессоров надо, чтобы ее выполнить, и сколько мощности она потребит.

У вас есть достаточное количество аналоговых компьютеров, каждый с достаточным количеством процессоров для любой задачи. Каждый компьютер может выполнять не более одной задачи в каждый момент времени, и не более чем две за все время. Первая задача может быть любой, вторая задача должна потреблять строго меньше мощности чем первая. Вы планируете назначить между одной и двумя задачами на каждый компьютер так, что каждая задача будет назначена ровно на один компьютер. Затем вы запустите первую задачу на каждом компьютере, подождете, пока они все выполнятся, и запустите вторую задачу на всех компьютерах, на которых назначено две задачи.

Если во время выполнения первых задач средняя мощность на процессор (сумма мощностей всех запущенных задач деленная на сумму занятых всеми задачами процессоров) превысит некоторую неизвестную величину, вся система взорвется после окончания вычислений, и вы не сможете выполнить вторые задачи. На вторые задачи такого ограничения нет. Найдите минимальную величину, которую не должна превышать средняя мощность на процессор, при которой возможно выполнить все задачи.

Ввиду специфики задачи, нужно найти ответ умноженный на 1000 и округленный вверх.

Входные данные

Первая строка содержит одно число n (1 ≤ n ≤ 50) — количество задач.

Вторая строка содержит n целых чисел a1, a2, ..., an (1 ≤ ai ≤ 108), где число ai задает мощность, которую потребит i-я задача.

Третья строка содержит n целых чисел b1, b2, ..., bn (1 ≤ bi ≤ 100) — где bi равно количеству процессоров, которые требуются для i-й задачи.

Выходные данные

Выведите одно число — минимальную величину, которую не должна превышать средняя мощность на процессор, при которой возможно назначить все задачи так, чтобы система не взорвалась после первого раунда, умноженную на 1000 и округленную вверх.

Примеры
Входные данные
6
8 10 9 9 8 10
1 1 1 1 1 1
Выходные данные
9000
Входные данные
6
8 10 9 9 8 10
1 10 5 5 1 10
Выходные данные
1160
Примечание

В первом примере оптимальная стратегия запустить каждую задачу на отдельном компьютере, получив среднюю мощность на процессор в первом (и единственном) раунде 9.

Во втором примере можно запустить задачи с потреблением мощности 10 и 9 на одном компьютере, задачи с потреблением 10 и 8 на втором, и задачи с потреблением 9 и 8 на третьем, получая среднюю нагрузку в первом раунде (10 + 10 + 9) / (10 + 10 + 5) = 1.16.