유효한 출발도시

시계 방향의 원형 도로로 연결된 도시가 있다고 상상해 보십시오. 각 도시에는 주유소가 있으며, 각 도시는 서로 멀리 떨어져 있습니다.

당신이 가지고 있는 자동차는 특정 마일리지를 갖고 있으며, 당신은 자동차에 기름을 채워서 어떤 한도시에서 출발한 후 각 도시에 있는 주유소에서 기름을 채우면서 모든 도시를 돌아 다시 출발지로 돌아올 수 있는 출발지를 선택해야 합니다.

이러한 도시는 유효한 출발도시라고 하며, 주어진 값에는 항상 유효한 출발도시가 하나 있습니다.

도시 사이의 거리를 나타내는 배열이 입력되고, 각 도시들은 원형 도로로 연결되어 있기 때문에, 마지막 도시는 첫번째 도시와 연결되어 있습니다. 즉, 거리 배열의 마지막 거리는 마지막 도시에서 첫번째 도시로의 거리와 같습니다. 또한 각 도시에서 사용할 수 있는 연료의 배열을 받게 됩니다. fuel[i]는 도시[i]에서 충전할 수 있는 연료의 양입니다. 항상 모든 도시를 여행하기에 충분한 연료가 제공됩니다. 연료 탱크는 항상 비어 있는 상태로 시작되며, 자동차의 연료 갤런당 이동할 수 있는 마일수(갤런당 마일 또는 MPG)는 양의 정수 값을 제공받습니다. 항상 최소 두개의 도시가 주어질 것입니다.

유효한 시작 도시의 인덱스를 반환하는 함수를 작성하세요.

예제 1

입력

distances = [5, 25, 15, 10, 15]
fuel = [1, 2, 1, 0, 3]
mpg = 10

출력

4