#include<iostream>
using namespace std;
int a[105],b[105];
int dp[105][105];
int n,m;
inline int min(int x,int y)
{
    return x<y?x:y;   
    }
inline int max(int x,int y)
{
    return x>y?x:y;   
    }
bool finish(int mid)
{
    int i,j,k,t;
    memset(dp,-1,sizeof(dp));
    dp[0][0]=0;
    for(i=1;i<=n;i++)
    {
        for(j=0;j<=m;j++)
        {
            for(k=0;k*a[i]<=mid;k++)
            {
                t=(mid-k*a[i])/b[i];
                if(j-k<0||dp[i-1][j-k]==-1)continue;
                dp[i][j]=max(dp[i-1][j-k]+t,dp[i][j]);
                if(j>=m&&dp[i][j]>=m)
                {
//                cout<<"dp["<<i-1<<"]["<<j-k<<"]="<<dp[i-1][j-k]<<endl;
//                cout<<"t="<<t<<endl;
//                cout<<"dp["<<i<<"]["<<j<<"]="<<dp[i][j]<<endl;
//                cout<<"mid="<<mid<<endl;
//                system("pause");
                return 1;
                }                   
                }                        
            }             
        }
    return 0;     
    }    
int main()
{
    int t,i,j,k,left,right,mid;
    scanf("%d",&t);
    while(t--)
    {
          scanf("%d%d",&n,&m);
          right=0;
          for(i=1;i<=n;i++)
          {
              scanf("%d%d",&a[i],&b[i]);
              right=max(max(a[i],b[i]),right);
              }
          right*=m;    
          left=1;
          while(left<=right)
          {
                mid=(left+right)>>1;
                if(finish(mid))right=mid-1;
                else left=mid+1;            
                }
//          if(finish(right))printf("%d\n",right);
          printf("%d\n",mid);      
          } 
    return 0;
    }