#include<fstream>
using namespace std;
int n, p, u, mid, i, j, k, L;
int a[101], b[101], d[101][101];
ifstream fin("lapte.in");
ofstream fout("lapte.out");
int verif(int t){
    for(int i = 1; i <= n; i++){
        for(int k = 1; k <= t / a[i]; k++){
            for(int j = k; j <= L - k; j++){
                int bl = (t - a[i] * k) / b[i];
                d[i][j] = d[i-1][j-k] + bl;
            }
        }
    }
    if(d[n][L] >= L){
        return 1;
    }
    return 0;
}
int main(){
    fin>> n >> L;
    for(i = 1; i <= n; i++){
        fin>> a[i] >> b[i];
    }
    p = 1;
    u = L * a[1] + L * b[1];
    while(p <= u){
        mid = (p + u) / 2;
        if(verif(mid)){
            u = mid - 1;
        }
        else{
            p = mid + 1;
        }
    }
    fout<< p <<"\n";
    return 0;
}