Statement

After many days of uninterrupted studying, William needs to take a break: a romantic trip with his girlfriend from Milan to Pordenone, to visit the famous Saint Valentine Park! During the travel, he will encounter N gas stations where he can buy some fuel for his car. William knows the price-per-liter P_i of each station and he has already estimated how much gasoline G_i at minimum he has to have at each station in order to reach the next one (and, at the last station, to arrive in Pordenone) safely. Being very wise, he brought with him many tanks so that he can buy as much gasoline as he wants. Help William plan how much he has to spend at minimum, knowing that he starts the journey from the first gas station without any fuel in the tanks.