No.25 Range of Influence

時間制限:$5.0sec$ / メモリ制限:$1GB$

問題

$N$ 軒の家が横一列に並んでおり、左から $i$ 番目の家を家 $i$ とします。
それぞれの家には価値と耐久性が決まっており、家 $i$ の価値は $A_i$ で、耐久性は $B_i$ です。
現在MAK君の勢力は $1\le i\le N$ を満たす家 $i$ です。MAK君の永遠のライバルであるculcul君はMAK君の勢力をなくそうと思いま した。
その方法は以下の通りです。なお、MAK君の勢力が $L\le i\le R$ を満たす家 $i$ だったとき、MAK君の勢力は $[L,R]$ と表すこと にします。

1. MAK君の勢力が $[L,R]$ であるとき、$L\le i\le R$ を満たす $i$ を選び、家 $i$ をつぶす。このとき、家$i$をつぶすのにかかる時間は $B_i$ になる。
   
2. $L=i=R$ が成り立つならばMAK君の勢力はなくなる。
   成り立たないならば、MAK君の勢力は $[L,i-1],[i+1,R]$ のどちらかになる。
   ここで、MAK君は自分の勢力が $[L,i-1],[i+1,R]$ になったときの、自分の勢力の範囲内にある家の価値の総和をそれぞれ計算して、
   より価値の総和が大きい勢力の範囲がMAK君の勢力になる。
   ただし、それぞれの価値の総和が同じならば、MAK君の勢力は $[L,i-1]$ になる。
   

culcul君はできるだけ短い時間でMAK君の勢力をなくそうと思いました。MAK君の勢力をなくすためにかかる時間の最小値を求めてください。
なお、家をつぶす時間以外は無視できるものとします。

制約

• $1 \le N \le 3000$
• $1 \le A_i \le 10^5$
• $1 \le B_i \le 10^5$

入力形式

入力は以下の形式で標準入力から与えられる。

N
A_1 A_2 … A_N
B_1 B_2 … B_N

出力

MAK君の勢力をなくすためにかかる時間の最小値を求めてください。

入出力例

4
1 2 3 4
4 3 2 1

3

以下のように家をつぶしていくと、最も短い時間でMAK君の勢力をなくすことができます。

1. 家 $3$ をつぶす $\rightarrow$ MAK君の勢力は $[4,4]$ になる。
   
2. 家 $4$ をつぶす $\rightarrow$ MAK君の勢力はなくなる。
   

5
2 3 9 4 1
4 2 1 5 2

7

以下のように家をつぶしていくと、最も短い時間でMAK君の勢力をなくすことができます。

1. 家 $3$ をつぶす $\rightarrow$ MAK君の勢力は $[1,2]$ になる。
   
2. 家 $1$ をつぶす $\rightarrow$ MAK君の勢力は $[2,2]$ になる。
   
3. 家 $2$ をつぶす $\rightarrow$ MAK君の勢力はなくなる。
   

1
100000
100000

100000

家が$1$軒のみしかない場合もあります。