FastPrep

Description

Solutions

Submission

Smart Gardener (Intuit India)

🤘 INTERN

Sam the gardener takes care for the garden in his area. One of the jobs in the garden is to water the garden. The garden has attached equidistant sprinklers, where each sprinkler has a range and a cost associated with it. Sam wants to switch on the sprinklers in such a way that whole garden is watered and the cost of this operation is minimised, so that he can use the money in some other gardening activities.

Can you help Sam in optimising the cost of watering the garden?

We can assume the garden to be on a x axis, where sprinklers are placed on every integer index from 0 to length of the garden. So, if the len of garden is n, then it has n + 1 sprinkles from 0 to n. If it is not possible to water the garden then return -1.

A sprinkler placed on index i with range r can water the garden from i-r to i+r.

Input Format

First line contains single integer N denoting the len of the garden.

Second line contains N + 1 space separated integers denoting the range of N + 1

Third line contains N + 1 space separated integers denoting the cost of N + 1 sprinkles

Output Format

Min cost of watering the garden

Example 1:

Input:  n = 4, range = [0, 0, 0, 0, 0], cost = [1, 2, 3, 4, 5]
Output: -1 
Explanation:
No explanation is provided for now...

Example 2:

Input:  n = 4, range = [1, 1, 2, 1, 0], cost = [5, 2, 5, 1, 1]
Output: 3 
Explanation:
No explanation is provided for now...

Constraints:

1 <= N <= 10^4

0 <= range[i] <= 100

0 <= cost[i] <= 10^4