512. CNG Refill

0

Medium

Baburao has planned a circular route with his girlfriend on her birthday. Along this route, there are

**n**CNG stations, each with a certain amount of CNG represented by**cng[i]**at the**i**station. Baburao's car has an unlimited capacity CNG tank, and it costs^{th}**price[i]**of CNG to travel from the**i**station to the next^{th}**(i+1)**station. Baburao will start the journey with an empty tank at one of the CNG stations. Help him determine the starting station.^{th}Input Format

Given two integer arrays

**cng**and**price**, input the size of the cng and price arrays.Output Format

If Baburao can travel around the circular route once in the clockwise direction, return the starting CNG station's index. Otherwise, return -1.

Example

Input

5
1 2 3 4 5
5
3 4 5 1 2

Output

3

Constraints

n == m == cng.length == price.length

1 <= n <= 105

0 <= cng[i], price[i] <= 104

1 <= n <= 105

0 <= cng[i], price[i] <= 104

Loading...

View Submissions

Console