問題文

今年の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$ つの小課題があります。

1. (400 点) $N \leq 5000$
2. (600 点) 追加の制約はない。

入力例1Copy

4
40 60 20 10
25 30 80 50

出力例1 Copy

95

入力例2 Copy

5
112 76 50 35 22
15 60 40 120 90

出力例2 Copy

140

入力例3 Copy

5
151 162 155 161 170
4 8 23 10 15

出力例3Copy

53