AT_abc404_e [ABC404E] Bowls and Beans

$ N $ 個の大きな茶碗が横一列に並んでおり、左から茶碗 $ 0,1,\dots,N-1 $ と番号付けされています。 茶碗 $ i $ ( $ 1 \le i \le N-1 $ ) には整数 $ C_i $ が書かれており、初めに中には $ A_i $ 個の豆が入っています。 茶碗 $ 0 $ に整数は書かれておらず、初めは豆も入っていません。 以下の操作を繰り返すことを考えます。 - ひとつの茶碗 $ i $ ( $ 1 \le i \le N-1 $ ) を選び、そこから $ 1 $ 個以上の豆を取り出す。 - 取り出した豆を、茶碗 $ i-C_i,i-C_i+1,\dots,i-1 $ に自由に振り分けて入れる。 - 厳密には、豆を $ k $ 個取り出した際、茶碗 $ i-C_i,i-C_i+1,\dots,i-1 $ に合計 $ k $ 個の豆を入れる。このとき、どの茶碗にいくつ豆を入れるかの振り分け方を任意に指定して入れる。 全ての豆が茶碗 $ 0 $ にある状態にするために必要な最小の操作回数を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ C_1 $ $ C_2 $ $ \dots $ $ C_{N-1} $ $ A_1 $ $ A_2 $ $ \dots $ $ A_{N-1} $

答えを整数として出力せよ。

### Sample Explanation 1 例えば以下の $ 3 $ 回の操作で全ての豆が茶碗 $ 0 $ にある状態にすることができ、これが最小です。 - 茶碗 $ 4 $ を選択する。この茶碗の中には豆が $ 1 $ つ入っている。 - 豆のうち $ 1 $ つを茶碗 $ 3 $ に入れる。 - 茶碗 $ 3 $ を選択する。この茶碗の中には豆が $ 1 $ つ入っている。 - 豆のうち $ 1 $ つを茶碗 $ 1 $ に入れる。 - 茶碗 $ 1 $ を選択する。この茶碗の中には豆が $ 2 $ つ入っている。 - 豆のうち $ 2 $ つを茶碗 $ 0 $ に入れる。 ### Sample Explanation 2 例えば以下の $ 4 $ 回の操作で全ての豆が茶碗 $ 0 $ にある状態にすることができ、これが最小です。 - 茶碗 $ 5 $ を選択する。この茶碗の中には豆が $ 1 $ つ入っている。 - 豆のうち $ 1 $ つを茶碗 $ 4 $ に入れる。 - 茶碗 $ 4 $ を選択する。この茶碗の中には豆が $ 2 $ つ入っている。 - 豆のうち $ 1 $ つを茶碗 $ 1 $ に入れる。 - 豆のうち $ 1 $ つを茶碗 $ 2 $ に入れる。 - 茶碗 $ 1 $ を選択する。この茶碗の中には豆が $ 2 $ つ入っている。 - 豆のうち $ 2 $ つを茶碗 $ 0 $ に入れる。 - 茶碗 $ 2 $ を選択する。この茶碗の中には豆が $ 2 $ つ入っている。 - 豆のうち $ 2 $ つを茶碗 $ 0 $ に入れる。 ### Constraints - 入力は全て整数 - $ 2 \le N \le 2000 $ - $ 1 \le C_i \le i $ - $ 0 \le A_i \le 1 $ - $ \displaystyle \sum_{i=1}^{N-1} A_i > 0 $