P12633 [UOI 2020] Skyscraper

1s 256M

Cossack Vus 住在一座摩天大楼里。 自从他开始从事建筑工作以来，$n$ 位客户委托他建造 $n$ 座摩天大楼。其中一座应距离 Cossack Vus 的摩天大楼 1 公里，另一座应距离 2 公里，第三座应距离 3 公里，以此类推。所有摩天大楼（包括 Cossack 的）必须位于同一条直线上，且他的摩天大楼位于最左侧。 第 $i$ 位客户希望他的摩天大楼高度为 $a_i$。然而，客户并不关心他们的摩天大楼距离 Vus 的摩天大楼有多远。因此，Cossack 可以自行决定其他摩天大楼相对于他的摩天大楼的建造顺序。 Cossack Vus 希望从他的摩天大楼看到的景色尽可能美丽。我们假设某一座摩天大楼的第 $i$ 层只有在没有其他摩天大楼的遮挡时，才能从 Vus 的摩天大楼看到。Cossack Vus 认为第 $i$ 座摩天大楼的每一层的美观度为 $b_i$。因此，他希望从他摩天大楼看到的所有楼层的总美观度尽可能大。  一个 $n=4$ 的例子。 图中展示了一个 $n=4$ 的例子。在 1 公里处建造了一座 2 层的摩天大楼，美观度为 $4$；接着是一座 1 层的摩天大楼，美观度为 $2$；然后是一座 3 层的摩天大楼，美观度为 $1$；最后是一座 4 层的摩天大楼，美观度为 $3$。从 Vus 的摩天大楼只能看到第一座摩天大楼的两层、第三座摩天大楼的第三层和第四座摩天大楼的第四层。因此，这些楼层的总美观度为 $4+4+1+3=12$。注意，这可能不是最优的建造顺序。 帮助他找到可能的最大美观度。

第一行包含一个整数 $n$（$1 \leq n \leq 10^5$）——需要建造的摩天大楼数量。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 10^9$）——摩天大楼的高度。 第三行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$（$1 \leq b_i \leq 10^9$）——摩天大楼各层的美观度。

输出一个整数——可能的最大总美观度。

- （$10$ 分）$1 \leq n \leq 10$，$1 \leq a_i \leq 10$，$1 \leq b_i \leq 10$； - （$27$ 分）$1 \leq n \leq 10^3$，$1 \leq a_i \leq 10^3$，$1 \leq b_i \leq 10^3$； - （$25$ 分）$1 \leq n \leq 10^3$，$1 \leq a_i \leq 10^9$，$1 \leq b_i \leq 10^9$； - （$38$ 分）无额外限制。 翻译由 DeepSeek V3 完成