Problem F: Puberty Rite[Hard]

Problem F: Puberty Rite[Hard]

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 1931  Solved: 173
[Submit][Status][Web Board]


A remote planet is called Joy. There is an ancient rule in Joy that every kid need to go for a hiking in dark forest to become an adult. This year, the kids of Joy that need to go for a hiking want to go together to ensure their safety. But they want to calculate a position to gather which minimizes the sum of their “distance”.

To simplify, we assume Joy is a straight line, every kid has a location xi on the line and every xi has a corresponding weight wi. As the gravitational force on Joy differs from earth, the “distance” between their home and the gathering position p need to be calculated as S3*Wi where S is |xi - p|.

In a word, we need to calculate the position p that minimize the total distance Σ( S3*Wi) where S is |xi - p|.


The first line of the input is the number T(T<=20), which is the number of test cases. The first line of each case has one integer N(1<=N<=50000), indicating the number of kids. Then comes N lines in the order that xi<=xi+1 for all i(1<=i<N). The ith line contains two real number : Xi,Wi, representing the location and the weight of the ith kid. ( |xi|<=106, 0<wi<15 )


For each test case, please output a line which is "Case #X: Y", X is the number of the test case and Y is the minimum sum of “distance” which is rounded to the nearest integer.

Sample Input

0.6 5
3.9 10
5.1 7
8.4 10

Sample Output

Case #1: 832


Triple search.