← 返回题目列表

Codeforces · 993/D

D. 计算能力

中文机器翻译题面 查看原题

您需要执行多个任务,每个任务都与其所需的处理器数量以及它将消耗的计算能力相关联。

您拥有足够数量的模拟计算机,每台计算机都有足够的处理器来完成任何任务。每台计算机一次最多可以执行一项任务,总共不超过两项任务。第一个任务可以是任何任务,每台计算机上的第二个任务必须使用严格少于第一个任务的电量。您将为每台计算机分配 1 到 2 个任务。然后,您将首先在每台计算机上执行第一个任务,等待所有任务完成,然后在分配了两个任务的每台计算机上执行第二个任务。

如果所有计算机上每个已使用处理器的平均计算能力(当前运行的所有任务的所有消耗功率的总和除以已使用处理器的数量)在执行第一个任务期间超过某个未知阈值,则整个系统将崩溃。第二个任务的执行没有限制。找出可能的最低阈值。

由于任务的特殊性,您需要打印乘以 1000 的答案并向上舍入。

输入

第一行包含一个整数 n (1 ≤ n ≤ 50) — 任务数。

第二行包含n个整数a1, a2, ..., an (1 ≤ ai ≤ 108),其中ai表示第i个任务所需的电量。

第三行包含 n 个整数 b1, b2, ..., bn (1 ≤ bi ≤ 100),其中 bi 是第 i 个任务将使用的处理器数量。

输出

打印一个整数值——可以分配所有任务的最低阈值,以使系统在第一轮计算后不会崩溃,乘以 1000 并向上舍入。

示例

输入 #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

注意

在第一个示例中,最佳策略是在单独的计算机上运行每个任务,使第一轮期间每个处理器的平均计算量等于 9。

在第二个任务中,最好在一台计算机上运行计算 10 和 9 的任务,在另一台计算机上运行计算 10 和 8 的任务,最后运行计算 9 和 8 的任务,在第一轮期间平均每个处理器的计算能力为 (10 + 10 + 9) / (10 + 10 + 5) = 1.16。