Gas Station

There are a total of n gas stations along a clockwise, circular route, and for the ith gas station (starting from 0), there are gas[i] litre of gas stored.

The distance between the ith gas station and the i + 1th gas station is dist[i].

You have a car, and you would like to travel clockwise starting from any gas station and return to the same gas station. The car has a sufficiently large gas tank, and for each unit of gas, your car can travel a unit distance. Initially, the fuel tank of your car is empty, but you can add fuel from any fuel station for as long as that fuel station has fuel left.

You wonder whether you can successfully travel this way. If so, output the index representing the starting gas station. Otherwise, output -1. The solution is guaranteed to be unique, if one exists.

Input

  • gas: a list of integers representing the gas available for each gas station.
  • dist: a list of integers representing the distance between each two adjacent gas stations.

Output

The unique starting gas station to be able to travel once, or -1 if no such station exists.

Examples

Example 1:

Input:

gas = [1, 2, 3, 4, 5]
dist = [3, 4, 5, 1, 2]

Output: 3

Explanation:

Starting from station 3, the car has 4 gas. It travels to the next station spending 1 gas, leaving 3 gas. Pick up 5 gas, travel to the next station, and leaving 6 gas. For the next three station, there is enough fuel to travel to each one and return to the starting point.

Constraints

  • 1 <= len(gas) == len(dist) <= 10^4
  • 1 <= gasi, disti <= 10^4

Try it yourself

Solution

Title

Script

Lorem Ipsum is simply dummy text of the printing and typesetting industry. Lorem Ipsum has been the industry's standard dummy text ever since the 1500s, when an unknown printer took a galley of type and scrambled it to make a type specimen book.

Contrary to popular belief, Lorem Ipsum is not simply random text.

  >>> a = [1, 2, 3]
  >>> a[-1]
  3

Get premium for instant access to all content and solutions

Upgrade