1 /*
 2 二分+DP。 
 3 二分时间t,dp[i][j]表示在时间t内前i个人完成j件A任务所能完成的B任务的最大数量。如果dp[i][x]>=y 
 4 就是可以的。然后不断迭代得到ans。
 5 */
 6 #include<iostream>
 7 using namespace std;
 8 #include<cstdio>
 9 #include<cstring>
10 #define N 70
11 int T,n,x,y,a[N],b[N];
12 void input(int &r)
13 {
14     memset(a,0,sizeof(a));
15     memset(b,0,sizeof(b));
16     scanf("%d%d%d",&n,&x,&y);
17     for(int i=1;i<=n;++i)
18     {
19         scanf("%d%d",&a[i],&b[i]);
20         r=max(r,max(a[i],b[i]));
21     }
22 }
23 bool check(int tim)
24 {
25     int f[230]={0};
26     memset(f,-1,sizeof(f));
27     f[0]=0;
28     for(int i=0;i<=x;++i)
29       if(tim>=a[1]*i)
30       f[i]=(tim-a[1]*i)/b[1];
31     if(f[x]>=y) return true;
32     for(int i=2;i<=n;++i)
33     {
34         for(int k=x;k>=0;--k)
35           for(int j=k;j>=0;--j)/*for(int j=0;j<=k;--j),结果更新f[i][k]的时候用的是他本身，如果改为for(int j=0;j<k;--j),又不能用f[i-1][k]来更新f[i][k]，所以就改为了倒序*/
36           if(tim>=(k-j)*a[i]&&f[j]!=-1)
37             f[k]=max(f[k],f[j]+(tim-a[i]*(k-j))/b[i]);
38        if(f[x]>=y) return true;
39     }
40     return false;
41 }
42 int find_ans(int l,int r)
43 {
44     int mid;
45     while(l<=r)
46     {
47         mid=(l+r)>>1;
48         if(check(mid))
49         {
50             r=mid-1;
51         }
52         else l=mid+1;
53     }
54     return l;
55 }
56 int main()
57 {
58     scanf("%d",&T);
59     int topt=0;
60     while(T--)
61     {
62         ++topt;
63         int l=1,r=0;
64         input(r);
65         r=r*2*max(x,y);
66         printf("Case %d: %d\n",topt,find_ans(l,r));
67     }
68     return 0;
69  }