Gas Station

There are n gas stations in a circle. At station i you gain gas[i] fuel and spend cost[i] to reach the next station. Return the starting station index that lets you complete the full circuit, or -1 if impossible (guaranteed at most one valid answer exists).

Example

Input: gas 1 2 3 4 5, cost 3 4 5 1 2 Output: 3

Approach

If the total gas across the whole circuit is less than the total cost, it's impossible outright — no starting point can work. Otherwise, walk through once tracking a running tank balance: whenever the tank goes negative, none of the stations you've tried so far (including the current one) can be the start, so reset the candidate start to the next station and the tank to zero. The station left standing at the end of this single pass is guaranteed to work, given the total-gas check passed.

Input format

Line 1: gas amounts, space-separated Line 2: costs, space-separated

Print the starting station index, or -1.