农历新年马上就要到了，奶牛们计划举办一次聚会庆祝新年的到来。但是，奶牛们并不喜欢走太远的路，这会给他们的聚会带来消极情绪，当一头奶牛的消极指数为 w_iwi​ ，他参加聚会所需行走的距离为 s_isi​ ，那么他就会给聚会带来 s_i^3*w_isi3​∗wi​的消极情绪。所有奶牛所在位置都在一条直线上，已知所有奶牛的坐标和消极指数，求如何确定聚会地点，使得所有奶牛给聚会带来的消极情绪之和最小，输出消极情绪之和的最小值。

 

输入格式

第一行包含一个整数 Ca ( Ca ≤ 20 ) ，表示有 Ca 组测试数据，对于每组测试数据：

第一行包含一个整数 n ( 1 ≤ n ≤ 50000 ) ，表示奶牛的数量。

接下来 n 行每行包含两个浮点数 x_ixi​ 和 w_iwi​ ( -10^6106≤ x_ixi​ ≤ 10^6106 ; 0 < w_iwi​ < 15 )。

 

输出格式

对于每组测试数据，输出 "Case #c: ans" ，其中 c 表示测试数据编号， ans 表示消极情绪之和的最小值，结果四舍五入为一个整数。

样例输入复制

150.9 21.4 43.1 16.2 18.3 2

样例输出复制

Case #1: 300

#include
       
        #include
        
         using namespace std;typedef long long ll;const int MAXN = 50010;const int inf = 0x3f3f3f3f;const double EPS = 1e-6;int t,n;double x[MAXN],w[MAXN];    //最好用全局变量，不用全局变量容易产生蜜汁错误double chu(double start)        //每一次把值算出来，找最小值{ double sum=0; for(int i=0;i
         
          >t;double l,r; for(int num=1;num<=t;num++) {  cin>>n;  l=inf,r=-inf;  for(int i=0;i
          
           >x[i]>>w[i];     if (x[i] > r)        r= x[i];    if (x[i] 
           
            EPS)            //三分法找最小值  {     double m1=(l+r)/2.0;     double m2=(m1+r)/2.0;     if(chu(m1)>chu(m2)) l=m1;     else r=m2;  } cout<<"Case #"<
            
             <<": "<< ll(chu(l)+0.5)<