import java.util.*;

class Cho{
    int x;
    int y;
    Map<Integer,Integer> map;
    public Cho(int x,int y) {
        this.x = x;
        this.y = y;
        this.map = new HashMap();
    }
}
public class Main{
    public static void main(String args[]){
    	Scanner scan = new Scanner(System.in);
    	int N = scan.nextInt();//N块
    	int K = scan.nextInt();//K人
    	int max = Integer.MAX_VALUE;//所有巧克力公共最大切法
    	List<Cho> chos = new ArrayList();
    	//枚举每块可能的切法
    	for(int i = 0;i < N;i ++) {
    		Cho cho = new Cho(scan.nextInt(),scan.nextInt());
    		//该块巧克力可能的最大边长切法
    		int minl = cho.x>cho.y?cho.x:cho.y;
    		for(int l = 1;l <= minl;l ++){
    			cho.map.put(l, (cho.x/l)*(cho.y/l));
    		}
    		chos.add(cho);
    		if(max > minl &&minl != 0)
    			max = minl;
    	}
    	int res = 0;//最终结果
    	//获取边长1~max切法切得的巧克力块数
    	for(int i = 1;i <= max;i ++) {
    		//边长i可切得的块数
    		int num = 0;
    		//遍历所有巧克力给num赋值
    		for(int j = 0;j < chos.size();j ++) {
    			num += chos.get(j).map.get(i);
    		}
    		//将符合人数且边长最大的切法作为res结果
    		if (num >= K) {
    			res = i;
    		}
    	}
    	System.out.print(res);
        scan.close();
    }
}