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.
## Input
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_ ≤ 108), 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.
## Output
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.
[samples]
## Note
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.
你需要执行若干任务，每个任务需要一定数量的处理器，并消耗一定的计算功率。
你拥有足够多的模拟计算机，每台计算机的处理器数量足以处理任意任务。每台计算机一次最多执行一个任务，总共最多执行两个任务。每台计算机上的第一个任务可以是任意的，但第二个任务的功率必须严格小于第一个任务。你将为每台计算机分配 1 到 2 个任务，然后先在所有计算机上同时执行第一个任务，等待它们全部完成，再在那些分配了两个任务的计算机上执行第二个任务。
如果在执行第一个任务期间，所有计算机中“每台已使用处理器的平均计算功率”（即所有正在运行任务的功率总和除以已使用处理器的总数）超过某个未知阈值，整个系统将爆炸。对第二个任务的执行没有限制。请找出使系统不会在第一轮计算后爆炸的最低阈值。
由于任务的特殊性，你需要输出该阈值乘以 1000 并向上取整后的结果。
第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 50]) —— 任务的数量。
第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an] (#cf_span[1 ≤ ai ≤ 108])，其中 #cf_span[ai] 表示第 #cf_span[i] 个任务所需的功率。
第三行包含 #cf_span[n] 个整数 #cf_span[b1, b2, ..., bn] (#cf_span[1 ≤ bi ≤ 100])，其中 #cf_span[bi] 表示第 #cf_span[i] 个任务将使用的处理器数量。
输出一个整数 —— 能够将所有任务分配，使得第一轮计算后系统不会爆炸的最低阈值，乘以 1000 并向上取整后的值。
在第一个例子中，最佳策略是将每个任务单独分配到一台计算机上，第一轮的平均每处理器计算功率为 9。
在第二个例子中，最佳策略是：一台计算机执行功率为 10 和 9 的任务，另一台执行功率为 10 和 8 的任务，最后一台执行功率为 9 和 8 的任务，第一轮的平均功率为 (10 + 10 + 9) / (10 + 10 + 5) = 1.16 每处理器。
## Input
第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 50]) —— 任务的数量。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an] (#cf_span[1 ≤ ai ≤ 108])，其中 #cf_span[ai] 表示第 #cf_span[i] 个任务所需的功率。第三行包含 #cf_span[n] 个整数 #cf_span[b1, b2, ..., bn] (#cf_span[1 ≤ bi ≤ 100])，其中 #cf_span[bi] 表示第 #cf_span[i] 个任务将使用的处理器数量。
## Output
输出一个整数 —— 能够将所有任务分配，使得第一轮计算后系统不会爆炸的最低阈值，乘以 1000 并向上取整后的值。
[samples]
## Note
在第一个例子中，最佳策略是将每个任务单独分配到一台计算机上，第一轮的平均每处理器计算功率为 9。在第二个例子中，最佳策略是：一台计算机执行功率为 10 和 9 的任务，另一台执行功率为 10 和 8 的任务，最后一台执行功率为 9 和 8 的任务，第一轮的平均功率为 (10 + 10 + 9) / (10 + 10 + 5) = 1.16 每处理器。
Let $ n $ be the number of tasks.
For each task $ i \in \{1, 2, \dots, n\} $, let:
- $ a_i $: compute power required,
- $ b_i $: number of processors utilized.
Each computer can execute **at most two tasks**:
- One **first task** (any),
- One **second task** (if any), with **strictly less power** than the first task on the same computer.
All tasks must be assigned.
First round: execute all **first tasks** simultaneously.
Second round: execute all **second tasks** (on computers with two tasks).
The system blows up if, during the **first round**, the average compute power per utilized processor exceeds a threshold $ T $:
$$
T = \frac{\sum_{\text{first tasks } i} a_i}{\sum_{\text{first tasks } i} b_i}
$$
We are to find the **minimum possible** value of $ T $ over all valid assignments of tasks to computers (satisfying the constraints), then output $ \lceil 1000 \cdot T \rceil $.
---
### Formal Mathematical Statement:
**Given:**
- Two sequences: $ \mathbf{a} = (a_1, \dots, a_n) \in \mathbb{Z}_{>0}^n $,
- $ \mathbf{b} = (b_1, \dots, b_n) \in \mathbb{Z}_{>0}^n $, with $ b_i \leq 100 $.
**Define:**
A **valid assignment** is a partition of the set of tasks $ \{1, \dots, n\} $ into disjoint subsets $ S_1, S_2, \dots, S_k $, each of size 1 or 2, such that:
- If $ |S_j| = 2 $, say $ S_j = \{i, i'\} $, then one task is designated as the **first** and the other as the **second**, with $ a_{\text{first}} > a_{\text{second}} $.
Let $ F \subseteq \{1, \dots, n\} $ be the set of **first tasks** (one per computer).
Let $ P_F = \sum_{i \in F} a_i $, $ Q_F = \sum_{i \in F} b_i $.
**Objective:**
Minimize
$$
T = \frac{P_F}{Q_F}
$$
over all valid assignments.
**Output:** $ \left\lceil 1000 \cdot \min T \right\rceil $
---
### Constraints Summary:
- Each computer: 1 or 2 tasks.
- If 2 tasks: first task power > second task power.
- All tasks assigned.
- Only first tasks contribute to $ T $.
- Minimize $ T = \frac{\sum a_i \text{ (first)}}{\sum b_i \text{ (first)}} $.
This is a **fractional programming** problem with pairing constraints. The goal is to **minimize the ratio** of total power to total processors over the set of first tasks, under the constraint that second tasks (if any) must have strictly less power than their paired first task.
This reduces to:
**Select a subset $ F \subseteq \{1,\dots,n\} $** (first tasks) and pair the remaining tasks $ R = \{1,\dots,n\} \setminus F $ into pairs $ (f, s) $ with $ f \in F $, $ s \in R $, such that $ a_f > a_s $, and each $ f \in F $ is paired with at most one $ s \in R $.
We want to minimize $ \frac{\sum_{i \in F} a_i}{\sum_{i \in F} b_i} $.
---
**Final Formal Statement:**
Let $ \mathcal{F} $ be the set of all subsets $ F \subseteq \{1, \dots, n\} $ such that the complement $ R = \{1, \dots, n\} \setminus F $ can be injectively mapped into $ F $ via a pairing function $ \pi: R \to F $ satisfying $ a_{\pi(s)} > a_s $ for all $ s \in R $, and $ |\pi^{-1}(f)| \leq 1 $ for all $ f \in F $.
Find:
$$
T^* = \min_{F \in \mathcal{F}} \frac{\sum_{i \in F} a_i}{\sum_{i \in F} b_i}
$$
Output: $ \left\lceil 1000 \cdot T^* \right\rceil $