1 /*
 2 Author:    Leo.W
 3 Descriptipn:    杀怪，以最少的失血杀掉所有的怪    。
 4 How to Do:    贪心算法，思想很好。对于杀怪顺序的权衡有这样的解释：
 5               A怪 杀伤ta，花费ca次杀此怪；B怪 杀伤tb，花费cb次；
 6               则若 (ta+tb)*ca+tb*cb<(ta+tb)*cb+ta*ca 即 需满足tb*ca<ta*tb 此时就先杀A怪
 7   */
 8 #include <stdio.h>
 9 #include <string.h>
10 #include <algorithm>
11 using namespace std;
12 #define MAXSIZES 10002
13 struct monster{
14     int hp;
15     int atk;
16     int counts;
17 };
18 monster mo[MAXSIZES];
19 int cmp(monster a,monster b){
20     return a.atk*b.counts>b.atk*a.counts;
21 }
22 int main(){
23     //freopen("in.txt","r",stdin);
24     int t,no=0;
25     scanf("%d",&t);
26     while(t--){
27         int i,mons,atk,sum=0;
28         __int64 all=0;
29         scanf("%d%d",&mons,&atk);
30         for(i=0;i<mons;i++){
31             scanf("%d%d",&mo[i].hp,&mo[i].atk);
32             if(mo[i].hp%atk==0)    mo[i].counts=mo[i].hp/atk;
33             else    mo[i].counts=mo[i].hp/atk+1;
34         }
35         sort(mo,mo+mons,cmp);
36         for(i=0;i<mons;i++){
37             sum+=mo[i].counts;
38             all+=sum*mo[i].atk;
39         }
40         printf("Case #%d: %I64d\n",++no,all);
41     }
42     return 0; 
43 }