题目描述

Shobon 决定使用生成式 AI 来帮助开发一个软件项目。该项目包含 $N$ 个任务。每个任务 $i$（$i=1,2,\ldots,N$）都有预先确定的实现工作量 $A_i$ 和复杂度 $B_i$。

Shobon 可以按任意顺序完成这些任务，但不能同时处理多个任务。

每个任务 $i$（$i=1,2,\ldots,N$）都可以用以下两种方式之一完成：

• 手动实现。 Shobon 自己编写代码，需要 $A_i$ 单位时间。
• 使用生成式 AI。 为了让 AI 生成正确的代码，Shobon 需要向 AI 解释当前任务以及此前所有已完成的任务。令 $S$ 为此前所有已完成任务的复杂度之和。准备这段说明需要 $S+B_i$ 单位时间。之后 AI 会瞬间完成实现，不需要额外的实现时间。因此，使用 AI 完成这个任务总共需要 $S+B_i$ 单位时间。

无论使用哪种方式，只要任务 $i$ 已经完成，它的复杂度 $B_i$ 就会计入此后使用生成式 AI 时的 $S$。

求完成所有任务所需的最少总时间。

输入格式

输入包含三行，格式如下。

N
A_1 A_2 ... A_N
B_1 B_2 ... B_N

第一行给出任务数 $N$（$1\le N\le 2\times 10^5$）。第二行包含 $N$ 个整数 $A_1,A_2,\ldots,A_N$，每个整数都在 $1$ 到 $10^9$ 之间（含端点），表示这 $N$ 个任务的实现工作量。第三行包含 $N$ 个整数 $B_1,B_2,\ldots,B_N$，每个整数都在 $1$ 到 $10^8$ 之间（含端点），表示这 $N$ 个任务的复杂度。

输出格式

在一行中输出完成所有任务所需的最少总时间。

3
10 6 10
5 2 4

18

1
4
10

4

5
100 100 100 100 100
5 1 4 2 3

35

12
18 7 25 12 30 5 16 22 9 28 14 20
6 11 2 8 1 13 5 3 10 4 9 7

118

提示

对于样例输入 1，可以依次使用生成式 AI 完成任务 $2$ 和 $3$，然后手动实现任务 $1$。

• 开始任务 $2$ 时，还没有完成任何任务。这个任务需要 $0+B_2=2$ 单位时间。
• 开始任务 $3$ 时，任务 $2$ 已经完成。这个任务需要 $B_2+B_3=2+4=6$ 单位时间。
• 最后，手动实现任务 $1$ 需要 $A_1=10$ 单位时间。

因此，可以用 $2+6+10=18$ 单位时间完成全部任务，这就是最少时间。