配点 : 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 有两个子作业。
- (400 点) N \leq 5000
- (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
作者: 岩哇哇