/ 
Time Limit: 4 sec / Memory Limit: 1024 MB
配点 : 1000 点
問題文
今年のPaken合宿には、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
writer: iwaiwaiwa