問題文

UT 鉄道 PC 本線は、1 本の路線に沿って N+1 個の駅が設置されていて、始発駅から終着駅まで順に 0,1,\ldots,N の番号が付いています。各 i (0\leq i\leq N-1) について、駅 i と駅 i+1 は隣り合っていて、この駅間の混雑度は C_i です。現在、駅 0, N には車両基地が併設されています。

次のダイヤ改正では、まず以下の操作を何回か繰り返すことで車両基地を建設します。

• ある i (1\leq i\leq N-1) を選び、駅 i に車両基地を併設する。これにはコスト A_i がかかる。

次に、以下の操作を何回か繰り返すことで車両基地間に列車を運行させます。

• 車両基地が併設されている駅 l,r (l < r) を選び、この間に列車を 1 本運行させる。このとき、駅 i と駅 i+1 の間 (l\leq i\lt r) の混雑度が 1 減少する。これにはコスト r-l がかかる。

ダイヤ改正の目標は、全ての i (0\leq i\leq N-1) について、駅 i と駅 i+1 の間の混雑度が 0 以下になるようにすることです。車両基地の建設および列車の運行に必要な総コストの最小値を求めてください。

制約

• 入力は全て整数
• 2 \leq N \leq 5\times 10^5
• 1 \leq C_i \leq 10^9 (0\leq i\leq N-1)
• 1 \leq A_i \leq 10^9 (1\leq i\leq N-1)

入力例 1

4
3 1 4 1
5 9 2

出力例 1

15

駅 3 に車両基地を併設し、駅 0,3 間に列車を 3 本、駅 0,4 間に列車を 1 本運行させます。すると、各駅間の混雑度は 0 以下になり、総コストは 15 となります。

入力例 2

9
28 35 19 27 84 98 78 79 60
40 35 54 63 72 71 27 94

出力例 2

682