A city bus runs on a circular route with n depots. The depots are numbered from 0 to n - 1, and after depot n - 1 the route comes back to depot 0. The bus tank can hold any amount of fuel, and the bus starts with an empty tank.
At depot i, the bus can fill gas[i] litres. The drive from depot i to the next depot uses cost[i] litres.
Choose the depot where the bus should start, so that it can drive once around the whole route in the order of the depots. Return the number of that depot. If no depot works, return -1. When a start works, it is the only one that does.
Examples
Example 1:
Input: gas = [3,1,5], cost = [4,3,2]
Output: 2
Explanation: Start at depot 2: fill 5, drive to depot 0 (3 litres left), fill 3 (6), drive to depot 1 (2), fill 1 (3), and drive back to depot 2 (0). The tank never goes below 0. Starting at depot 0 or 1 fails.
Example 2:
Input: gas = [2,2,2], cost = [3,3,3]
Output: -1
Explanation: All the depots together give less fuel than the whole route needs.
Example 3:
Input: gas = [3], cost = [2]
Output: 0
Explanation: With one depot, the fuel taken there is enough for the one drive around.