#include<iostream>
using namespace std;
main()
{
     int cas;
     scanf("%d",&cas);
     int n,m;
     int wer[101][2];
     int dp[101][101];
     int d,p,s;
     int head,end,mid;
     int max1,max2;
     int flag;
     int y;
     while (cas--)
     {
         head=end=1;
         max1=max2=0;
         scanf("%d %d",&n,&m);
         for (d=1;d<=n;d++)
         {
             scanf("%d %d",&wer[d][0],&wer[d][1]);
             max1=max(wer[d][0],max1);
             max2=max(wer[d][1],max2);
         }
         end=m*(max1+max2);
         while (head<=end)
         {
             mid=(head+end)/2;
             flag=0;
             memset(dp,-1,sizeof(dp));
             for(d=0;d<=n;d++)
             dp[d][0]=0;
             if (!flag)
                 for (d=1;d<=n;d++)
                     if (!flag)
                         for (p=0;p<=m;p++)
                             if (!flag)
                             {
                                 for (s=0;s<=p;s++)
                                 {


                                     if (mid-s*wer[d][0]>=0&&dp[d-1][p-s]!=-1)
                                     {
                                         y=(mid-s*wer[d][0])/wer[d][1];
                                         dp[d][p]=max(dp[d][p],dp[d-1][p-s]+y);
                                         if (p==m)
                                             if (dp[d][p]>=m)
                                             {
                                                 flag=1;
                                                 break;
                                             }
                                     }
                                 }
                             }
             if (flag==0)
                 head=mid+1;
             else
                 end=mid-1;
         }
         printf("%d\n",head);
     }
     return 0;
}