You are given a set of cities that are laid out in a circle, connected by a circular road that runs

clockwise. Each city has a gas station that provides gallons of fuel, and the distances between these

cities are known. You have a car that can drive some number of miles per gallon of fuel, and your

goal is to pick a starting city such that you can fill up your car in that city $($using that city's gas

station$).$ You can then drive to the next city, refill up your car with that city's fuel, drive to the next

city, and so on and so forth until you return back to the starting city with $0$ or more gallons of fuel

left. $0$This city is called a preferred starting city. In this problem, it is guaranteed that there will

always be exactly one valid starting City

The problem set involves series of arrays. The first array is the distance between neighboring cities.

Assume that city $i$ is distances i away from city $i+1.$ Since the cities are connected via a

circular road, the last city is connected to the first city. In other words, the last distance in the

distances array is equal to the distance from the last city to the first city. The second array is an

array of gas available at each city, where gas $i$ is equal to the gas available at city $i.$ The total

amount of gas available $($from all gas stations$)$ is enough to travel to all cities. Your gas tank always

starts out empty, and a positive integer value for the number of miles that your car can travel per

gallon of fuel $($miles per gallon, or MPG$)$ is also given.

Write a function that returns the index of the preferred starting city.

Sample Input:

$cit{y}_d$istances $=,[5,25,15,10,15]$

fuel $=,[1,2,1,0,3]$

$mpg=,10$

The preferred starting city for the sample above is city $4$

$1.$Develop a complete and clear pseudocode

$2.$ Mathematically analyze your pseudocode and prove the efficiency class, using either induction, limits or step counts. State the method used

$3.$ Please write it in C$++$