Compute Power

题意翻译

你有 $n$ 个任务需要分配，其中第 $i$ 个任务要使用 $a_i$ 的功率和 $b_i$ 个处理器。 给你无限台计算机，每台计算机可以处理一个或两个任务，要求第二个任务的需求功率要严格小于第一个任务。最小化所有计算机处理第一个任务的处理器平均功率（所有第一个任务的功率和/所有第一个任务使用的处理器数量和）。 结果可能是一个小数，请将其乘以 $1000$，向上取整后保留整数输出。

题目描述

You need to execute several tasks, each associated with number of processors it needs, and the compute power it will consume. You have sufficient number of analog computers, each with enough processors for any task. Each computer can execute up to one task at a time, and no more than two tasks total. The first task can be any, the second task on each computer must use strictly less power than the first. You will assign between 1 and 2 tasks to each computer. You will then first execute the first task on each computer, wait for all of them to complete, and then execute the second task on each computer that has two tasks assigned. If the average compute power per utilized processor (the sum of all consumed powers for all tasks presently running divided by the number of utilized processors) across all computers exceeds some unknown threshold during the execution of the first tasks, the entire system will blow up. There is no restriction on the second tasks execution. Find the lowest threshold for which it is possible. Due to the specifics of the task, you need to print the answer multiplied by 1000 and rounded up.

输入输出格式

输入格式

The first line contains a single integer $ n $ ( $ 1<=n<=50 $ ) — the number of tasks. The second line contains $ n $ integers $ a_{1},a_{2},...,a_{n} $ ( $ 1<=a_{i}<=10^{8} $ ), where $ a_{i} $ represents the amount of power required for the $ i $ -th task. The third line contains $ n $ integers $ b_{1},b_{2},...,b_{n} $ ( $ 1<=b_{i}<=100 $ ), where $ b_{i} $ is the number of processors that $ i $ -th task will utilize.

输出格式

Print a single integer value — the lowest threshold for which it is possible to assign all tasks in such a way that the system will not blow up after the first round of computation, multiplied by 1000 and rounded up.

输入输出样例

输入样例 #1

6
8 10 9 9 8 10
1 1 1 1 1 1

输出样例 #1

9000

输入样例 #2

6
8 10 9 9 8 10
1 10 5 5 1 10

输出样例 #2

1160

说明

In the first example the best strategy is to run each task on a separate computer, getting average compute per processor during the first round equal to 9. In the second task it is best to run tasks with compute 10 and 9 on one computer, tasks with compute 10 and 8 on another, and tasks with compute 9 and 8 on the last, averaging (10 + 10 + 9) / (10 + 10 + 5) = 1.16 compute power per processor during the first round.