2014
02-10

# 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.

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.

1
4
1 2
2 1
3 3
1 1

3

1. 狗作为人类的宠物和劳动伙伴，被驯化的历史一般认为最长达1.5万年之久，狗与人的关系远非其他可食用物种可比，不能简单类比。

2. 狗作为人类的宠物和劳动伙伴，被驯化的历史一般认为最长达1.5万年之久，狗与人的关系远非其他可食用物种可比，不能简单类比。

3. 狗作为人类的宠物和劳动伙伴，被驯化的历史一般认为最长达1.5万年之久，狗与人的关系远非其他可食用物种可比，不能简单类比。

4. 站长，你好！
你创办的的网站非常好，为我们学习算法练习编程提供了一个很好的平台，我想给你提个小建议，就是要能把每道题目的难度标出来就好了，这样我们学习起来会有一个循序渐进的过程！