View Code of Problem 1058

import java.util.Scanner;

public class Main{
	static int  N =102;
	static int[] a=new int[N];
    static int[] b=new int[N];
	static int[] dp=new int[N];
	static int n,m;
	static boolean judge(int time){ 
		for(int i=0;i<N;i++){
	    	dp[i]=-1;
	    }
	    dp[0]=0;
	    for(int i=0;i<n;i++){
	       for(int j=m;j>=0;j--)
	            if(dp[j] != -1){
	                for(int k=m;k>=0;k--){
	                    if(a[i]*k <= time && j+k <= m)
	                         dp[j+k]=Math.max(dp[j+k],dp[j]+(time-a[i]*k)/b[i]);
	                 }
	             }
	        }
	  return dp[m] >= m;
	}
	 
  public static void main(String args[]){
	 Scanner sc=new Scanner(System.in);
	 int cas=sc.nextInt();
	 while(cas--!=0){
	    n=sc.nextInt();
	    m=sc.nextInt();
	    int max_time=-1;
        for(int i=0;i<n;i++){
        	a[i]=sc.nextInt();
        	b[i]=sc.nextInt();
        	max_time=Math.max(max_time,a[i]);
	        max_time=Math.max(max_time,b[i]);
        }
        max_time=max_time*m*2;
        int left,right,mid;
        int min_time=0;
        left=1;
        right=max_time;
        while(left <= right){
            mid=(left+right)>>1;
            if(judge(mid)){
                right=mid-1;
                min_time=mid;
            }
            else
                left=mid+1;
        }
	 System.out.println(min_time);
    }
  }
}