AT_tkppc4_1_o Height Changer

[problemUrl]: https://atcoder.jp/contests/tkppc4-1/tasks/tkppc4_1_o 今年のPaken合宿には、$ N $ 人が参加します。さて、今部員全員が講義会場に到着しました。左端の画面にはスライドが映っています。しかし、会場が狭く、部員たちは左から右へ一列に並ぶことになりました。このとき、各部員には左から順に、$ 1 $ から $ N $という番号がついています。 この集団では、スライドに近い方からレートの高い順に並ぶ文化があるため、並びを変えることはできません。しかし、参加者たちの身長は様々なので、このままだと身長の低い人が画面を見られなくなってしまうかもしれません。 そこで、魔法少年のOsmium\_1008君は、いくつかの部員の身長を縮める魔法を使うことにしました（Osmium\_1008君は魔法によって身長を縮めることはできますが、伸ばすことはできません）。 部員 $ i $ の身長は $ A_i $ で、スライドを見られた時の嬉しさは $ B_i $ で表されます。 また、自分より左側 (自分より番号が小さい) にいる人の中で自分より身長が真に高い人がいる場合（**同じ場合は見られます**）、その人はスライドを見られず、嬉しさは $ 0 $ になります。 また、Osmium\_1008君が魔法を使った場合、身長を縮められた部員は縮められた長さ分だけ嬉しさが**さらに**減ります。 全員の嬉しさの合計の最大値を求めてください。ただし、Osmium\_1008君は一度も魔法を使わないこともできます。また、各人の嬉しさの値が負になることもあります。

入力は以下の形式で標準入力から与えられる。 > $ N $ > $ A_1 $ $ A_2 $ $ \ldots $ $ A_{N-1} $ $ A_N $ > $ B_1 $ $ B_2 $ $ \ldots $ $ B_{N-1} $ $ B_N $

全員の嬉しさの合計の最大値を $ 1 $ 行に出力してください。

### 制約 - 入力は全て整数である。 - $ 1\leq\ N\leq\ 10^5 $ - $ 1\leq\ A_i,B_i\leq\ 10^9 $ ### 小課題 この課題には $ 2 $ つの小課題があります。 1. (400 点) $ N\ \leq\ 5000 $ 2. (600 点) 追加の制約はない。