Garbage collecting station

As everyone knows, the garbage collecting station is very important to our daily life. With the growing of the city, more and more garbage need to be collected timely. First, let us see what will the garbage collecting station do everyday.
The station divide the city into N*M blocks, each block contains some buindings, as the picture below shows. And the garbage collecting station lies at the suburban district, but not inside any one of these blocks.


The station will sort the blocks (b1, b2, … bK, K = N*M )by their priority in a line. For instance, after the sort process, the blocks will be arranged as a sequence b1. b2. b3….bK, then the garbage collecting lorry will begin to collect garbage at b1, loading the garbage at b1, then go to b2, loading garbage then go to b3, and so on. After loaded the garbage at bK, the lorry will go to the station and upload all the garbage.

Now the station want to build another two stations, and these two stations will build inside two different blocks bi and bj (i<j). And the garbage of blocks b1 to bi will be carried to bi, the garbage of blocks bi+1 to bj will be carried to bj, the garbage of blocks bj+1 to bK will be carried to the station at the suburban district.

Now the problem is: we assume that carrying one unit of garbage in one meter will cost $1. Given the weight of the garbage of each block and the distance between bi and bi+1(1<=i<k), bk and the station, you should find out where to build the two new stations(i.e, choose two blocks bi and bj and make them as new stations) to make the cost as low as possible.

Standard input will contain multiple test cases. The first line of the input is a single integer T which is the number of test cases. T test cases follow.
The first line of each test case contains an integer N(1<=N<=10000), the number of blocks. N lines follow. The i-th line containing two integers, wi (the weight of garbage of block i, 1<=wi<=10000) and di(the distance between di and di+1, 1<=di<=10000), the last one dk means the distance between dk and the station.

Results should be directed to standard output. For each case, output an integers S, the least $ we have to spend to carry the garbage to the collecting station.

1
4
1 2
2 1
3 3
1 1

3

2008 HZNU Programming Contest