#include <fstream>
#include <vector>
#define MAX 100

using namespace std;
ifstream fin ("lapte.in");
ofstream fout ("lapte.out");
int a[MAX];
int b[MAX];
int n,k,ok;
int rez[MAX][MAX];
int solve (int t) {
    vector<int> dp(k+1, -1);
    dp[0]=0;
    for (int i=0; i<n; i++) {
        vector<int> curr(k+1, -1);
        for (int x=0; x*a[i]<=t; x++) {
            int y=(t-x*a[i])/b[i];
            for (int j=0; j<=k; j++) {
                if (dp[j]!=-1) {
                    int nou=min(k, j+x);
                    if (dp[j]+y>curr[nou]) {
                        curr[nou]=dp[j]+y;
                    }
                }
            }
        }
        dp=curr;
    }
    return dp[k]>=k;
}
int main() {
    int i,st,dr,mij,sol,curr,prec,x,y;
    fin>>n>>k;
    for (i=0; i<n; i++) {
        fin>>a[i]>>b[i];
    }
    st=0;
    dr=1e4;
    while (st<=dr) {
        mij=(st+dr)/2;
        if (solve(mij)) {
            sol=mij;
            dr=mij-1;
        } else {
            st=mij+1;
        }
    }
    fout<<sol<<endl;
    return 0;
}