Where to Build a Brewery?

The residents of the island of Abstinence love alcohol-free beer. Until now it was imported from Poland, but this year one of the island's cities will build a brewery. Every city sits on the coast, and they are all linked by a single highway that runs around the island along the shore, so the cities form one big ring. The investor has gathered, for every city, the number of beer tanks it needs each day (its demand) and the distances between neighbouring cities. Moving one tank of beer one mile costs 1 thaler. The daily transport cost is the total cost of shipping the required number of tanks from the brewery to every city, where the beer for each city travels along the shorter of the two directions around the ring. This cost depends on where the brewery is built, and the investor wants to choose the city that makes it as small as possible.

Write a program that

• reads the number of cities, the distances between them, and each city's daily beer demand,
• computes the minimal daily transport cost,
• writes the result to standard output.

The first line contains one integer $n$, the number of cities ($5 \le n \le 10\,000$). Cities are numbered along the highway, so neighbouring cities have consecutive numbers, and cities $1$ and $n$ are neighbours too. Each of the next $n$ lines contains two non-negative integers separated by a single space: $z_i$ and $d_i$. Here $z_i$ is the daily beer demand of city $i$, and $d_i$ is the distance in miles from city $i$ to the next city along the highway. The total length of the highway does not exceed $1\,000\,000$ miles. The demand of each city does not exceed $1\,000$ tanks.

Print a single integer: the minimal daily transport cost.