← 返回题目列表

AtCoder · tkppc4_1_o

O. 高度调节器

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

配点 : 1000 点

問題文

在今年的帕肯训练营中,N 人们参与。目前所有会员均已抵达讲座地点。最左边的屏幕上会显示一张幻灯片。但场地狭小,成员们必须从左到右排队。这时,每个成员,从左到右, 它的编号为1 减去 N。
该组有一种从最接近幻灯片的评分开始按评分降序排列的文化,因此无法更改顺序。然而,参与者的身高各不相同,所以如果这种情况持续下去,矮个子可能看不到屏幕。

因此,魔法少年Osmium_1008决定使用魔法来缩短部分俱乐部成员的身高(Osmium_1008可以用魔法缩短身高,但不能增加身高)。

部員 i 的高度是 A_i 所以,当我看到幻灯片时我是多么高兴。 由 B_i 代表。 另外,如果你左边有一个人(数字比你低)确实比你高(可以看到相同的情况),这个人看不到幻灯片,幸福感是 0 。
另外,当Osmium_1008使用魔法时,身高被缩短的成员会因为身高缩短的长度而感到高兴。另外将减少。

求每个人总幸福感的最大值。然而,Osmium_1008也永远无法使用魔法。而且,每个人的幸福值都可能是负数。

制約

  • 所有输入均为整数。
  • 1\leq N\leq 10^5
  • 1\leq A_i,B_i\leq 10^9

小課題

这项作业需要 2 有两个子作业。

  1. (400 点) N \leq 5000
  2. (600分)没有额外的限制。

入力

输入是按以下格式从标准输入给出的。

N
A_1 A_2 \ldots A_{N-1} A_N
B_1 B_2 \ldots B_{N-1} B_N

出力

每个人的总幸福值最大值 请在 1 行输出。

注意

小課題 1 的代码时, 我们建议添加一个进程,如果该值大于N 是 在 5000 ,该进程将立即终止。


入力例1

4
40 60 20 10
25 30 80 50

出力例1

95

Osmium_1008 您是会员 1 的高度 30、部員 2 的高度 50、部員 3 的高度 10 通过减少幸福感的总和 95 可以实现。


入力例2

5
112 76 50 35 22
15 60 40 120 90

出力例2

140

入力例3

5
151 162 155 161 170
4 8 23 10 15

出力例3

53

作者: 岩哇哇