#include<iostream>

 #include<cstdio>

 #include<cmath>

 #include<algorithm>

 #include<cstring>

 #include<set>

 #include<vector>

 #define ll long long

 #define M 55

 #define inf 1e10

 #define mod 1000000007

 using namespace std;

 struct point

 {

     int x,y;

     double k;

     bool operator<(const point &a) const

     {

         return k>a.k;

     }

 }p[M];

 int dp[M*M][M];

 int main()

 {

     int i,j,m,t,ca=,n,k;

     scanf("%d",&t);

     while(t--){

         scanf("%d%d",&n,&k);

         memset(dp,-,sizeof(dp));

         dp[][]=;

         for(i=;i<n;i++){

             scanf("%d%d",&p[i].x,&p[i].y);

             if(p[i].x==) p[i].k=inf;

             else p[i].k=1.0*p[i].y/p[i].x;

         }

         sort(p,p+n);

         int ans=;

         for(i=;i<n;i++)

         for(j=M*M-;j>=;j--){

             for(int l=k-;l>=;l--)

             if(dp[j][l]>=){

                 int tt=(p[i].y+*j)*p[i].x+dp[j][l];

                 dp[j+p[i].y][l+]=max(dp[j+p[i].y][l+],tt);

             }

         }

         for(i=M*M-;i>=;i--) ans=max(ans,dp[i][k]);

         printf("Case %d: %d\n",++ca,ans);

     }

     return ;

 }