Smart Gardener (Intuit India)

The garden is the continuous interval [0,N], and there is one sprinkler at each position 0 through N. A sprinkler at position i with range r waters the closed interval [i-r,i+r]; turning on a sprinkler incurs its cost once. Find the minimum total cost to cover the whole garden, or output -1 if it cannot be covered.

输入格式

The input gives N (1≤N≤10000), then a line of N+1 ranges (0..100), then a line of N+1 costs (0..10000).

输出格式

Output the answer as described; for array answers, separate values with spaces.

样例 1

输入：

3
1 0 0 1
3 5 5 3

输出：

-1

样例 2

输入：

4
0 0 0 0 0
1 1 1 1 1

输出：

-1

样例 3

输入：

2
2 0 0
7 0 0

输出：

7

样例说明

Interval-cover dynamic programming: dp[x] is the minimum cost to cover [0,x]. When a sprinkler extends a covered prefix, the end of the prefix must lie within the sprinkler's coverage interval; use the upper bound on the radius to scan predecessors directly.

Correctness: any optimal plan, taken in the order the sprinklers are turned on, can be viewed as a chain of overlapping intervals that extends to the right. The last sprinkler can continue from any covered end L≤x<R to cover up to R; conversely, every such extension keeps the prefix free of gaps. Therefore, processing right endpoints in increasing order, taking the minimum dp value over all valid predecessors, and enumerating every possible last sprinkler yields the optimum.

Complexity: O(N·201) time, O(N) space. Costs are non-negative, and the answer is at most 100010000.