AT_abc404_e [ABC404E] Bowls and Beans

There are $ N $ large bowls arranged in a row, numbered $ 0,1,\dots,N-1 $ from the left. For each bowl $ i $ ( $ 1\le i\le N-1 $ ), an integer $ C_i $ is written on it, and initially it contains $ A_i $ beans. Bowl $ 0 $ has no integer written on it and initially contains no beans. Consider repeating the following operation any number of times: - Choose one bowl $ i $ ( $ 1\le i\le N-1 $ ) and take out one or more beans from it. - Distribute the taken beans freely among bowls $ i-C_i,i-C_i+1,\dots,i-1 $ . - Formally, when you take out $ k $ beans, you must put a total of $ k $ beans into bowls $ i-C_i,i-C_i+1,\dots,i-1 $ , and you may choose how many beans go into each bowl. Find the minimum number of operations required to put all the beans into bowl $ 0 $ .

The input is given from Standard Input in the following format: > $ N $ $ C_1 $ $ C_2 $ $ \dots $ $ C_{N-1} $ $ A_1 $ $ A_2 $ $ \dots $ $ A_{N-1} $

Output the answer as an integer.

### Sample Explanation 1 For example, the following three operations put all the beans into bowl $ 0 $ , and this is the minimum: - Choose bowl $ 4 $ . It has $ 1 $ bean. - Put $ 1 $ bean into bowl $ 3 $ . - Choose bowl $ 3 $ . It has $ 1 $ bean. - Put $ 1 $ bean into bowl $ 1 $ . - Choose bowl $ 1 $ . It has $ 2 $ beans. - Put $ 2 $ beans into bowl $ 0 $ . ### Sample Explanation 2 For example, the following four operations put all the beans into bowl $ 0 $ , and this is the minimum: - Choose bowl $ 5 $ . It has $ 1 $ bean. - Put $ 1 $ bean into bowl $ 4 $ . - Choose bowl $ 4 $ . It has $ 2 $ beans. - Put $ 1 $ bean into bowl $ 1 $ . - Put $ 1 $ bean into bowl $ 2 $ . - Choose bowl $ 1 $ . It has $ 2 $ beans. - Put $ 2 $ beans into bowl $ 0 $ . - Choose bowl $ 2 $ . It has $ 2 $ beans. - Put $ 2 $ beans into bowl $ 0 $ . ### Constraints - All input values are integers. - $ 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 $