You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

时空限制

1S/512M

题目描述

作为一名勇者，apiadu 正在与一头巨龙进行决战。这场战斗将持续 $n$ 个回合。

在第 $i$ 个回合，apiadu 可以从以下两种行动中选择一个：

• 提高攻击力：apiadu 花费整个回合来吟唱古老的咒语，这会使他的攻击力永久提升 $a_i$ 点。
• 攻击：apiadu 释放一道强大的能量冲击波攻击巨龙。冲击波的伤害值为他当前的攻击力 + $b_i$ 。

apiadu 的初始攻击力为 $0$。他的目标是合理安排每个回合的行动，使得在 $n$ 回合结束后，对巨龙造成的总伤害最高。请你帮他计算能造成的最多伤害。

格式

输入格式

第一行包含一个整数 $n$，表示战斗的回合数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，具体意义如题面所示。

第三行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$，具体意义如题面所示。

输出格式

输出一个整数，表示可以造成的最大总伤害。

样例

样例输入 #1

4
3 5 2 7
8 4 9 3

样例输出 #1

30

样例解释 #1

一种可以获得最大总伤害的策略如下：

• 回合 $1$：选择攻击。造成 $8$ 点伤害。

• 回合 $2$：选择提升攻击力。此时攻击力为 $5$。

• 回合 $3$：选择攻击。造成 $9 + 5 = 14$ 点伤害。

• 回合 $4$：选择攻击。造成 $5 + 3 = 8$ 点伤害。

• 最终对巨龙造成的总伤害为 $8 + 14 + 8 = 30$。

数据规模

对于 $30\%$ 的数据，$1\leq n \leq 1000$，$1 \leq \sum_{i =1}^{n} a_i \leq 3000$。

对于 $100\%$ 的数据，$1 \leq n \leq 3000$，$1 \leq a_i, b_i \leq 10^9$。