BROW  A place for the brewery
The dwellers of the island Abstinence are very fond of alkoholfree beer. Hitherto alkoholfree beer was imported from Poland, but this year one of the cities on Abstinence is going to build a brewery. All the cities of this island lie on the coast and are connected by a highway running around the island along its shore. The investor building the brewery collected information about the demand for beer, i.e. how many tanks of beer are needed daily in each city. He has also a table of distances between cities. The cost of transporting one tank is 1 thaler per mile. A daily cost of transport is the amount of money, which has to be spent on transporting a necessary number of tanks of beer from the brewery to each city. The daily cost depends on the location of the brewery. The investor wants to find a location that minimizes the daily cost.
Task
Write a program which
 reads the number of cities, distances between them and daily requests for beer,
 computes the minimal daily cost of transport,
 writes the result.
Input
There are multiple test cases. Their number is given in the first line of input. In the first line of each test case there is one integer n  the number of cities, 5 <= n <= 10 000. (We assume that cities are numbered along the highway, so that the neighbouring cities have subsequent numbers. Cities 1 and n are neighbours too.) In each of the following n lines there are two nonnegative numbers separated by a single space. Numbers zi di written in the line (i+1) are respectively the demand for beer in the city i and the distance (in miles) from city i to the next city on the highway. The entire length of the highway is not greater than 1 000 000 miles. The demand for beer in each city is not greater than 1 000 tanks.
Output
For each test case your program should write only one line  exactly one integer equal to the minimal daily cost of transport.
Example
Input: 1 6 1 2 2 3 1 2 5 2 1 10 2 3 Output: 41
hide comments
Ashwini:
20131222 12:42:02
@ JaceTheMindSculptor : its city i suppose 

Ashwini:
20131222 12:40:56
isn't O(n^2) not sufficient?? I,m getting tle' 

Viktor Fonic:
20130730 15:02:37
You can have multiple trucks. 

LeppyR64:
20110715 11:22:32
Does the truck travel only one direction? If the truck can travel multiple ways, can the truck carry only some beer and then reload? 

:D:
20100413 14:07:21
In a city. 

JaceTheMindSculptor:
20090315 19:36:13
Does the brewery have to be built ina city? On a highway? On a certain point in the centre of hte island to be connected to other cities? 
Added by:  PaweÅ‚ Dobrzycki 
Date:  20051221 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: NODEJS PERL6 VB.NET 
Resource:  VII Polish Olympiad in Informatics, Ist Stage 