Gas Station

Medium

greedyarray

There are n gas stations on a circle. gas[i] is fuel available at station i; cost[i] is fuel needed to drive to station i+1. Starting empty at some station, return the index from which you can complete one full clockwise circuit, or -1. The answer is unique when it exists.

Input

Line 1: space-separated gas
Line 2: space-separated cost

Output: the starting index, or -1.

Example 1

Input:

1 2 3 4 5
3 4 5 1 2

Output:

Example 2

Input:

2 3 4
3 4 3

Output:

-1

Constraints

1 ≤ n ≤ 10^5

Watch a video walkthrough

Run your code against the sample tests, or Submit to run the full suite.

Problems

Gas Station

Medium

greedyarray

Input

Line 1: space-separated gas
Line 2: space-separated cost

Output: the starting index, or -1.

Example 1

Input:

1 2 3 4 5
3 4 5 1 2

Output:

Example 2

Input:

2 3 4
3 4 3

Output:

-1

Constraints

1 ≤ n ≤ 10^5

Watch a video walkthrough

Run your code against the sample tests, or Submit to run the full suite.