#include <fstream>

using namespace std;
ifstream in("lapte.in");
ofstream out("lapte.out");
int nrpers,cantminim;
int a[101],b[101];
int maxva=0;
int maxvb=0;
int timp_presupus;
int tfinal;
int dp[101][101];///primele i persoane beau j litri de lapte b,unde dp[i][j] e cant max lapte b

bool posibil(int t)
{
    for(int i=0; i<=nrpers; i++)
        for(int j=0; j<=cantminim; j++)
            dp[i][j]=-2000000000;
    dp[0][0]=0;
    for(int i=1; i<=nrpers; i++)
        for(int j=0; j<=cantminim; j++)
            for(int a1=0; a1<=j; a1++)
            {
                if(a[i]*a1<=t)
                    dp[i][j]=max((dp[i-1][j-a1]+((t-a[i]*a1)/b[i])),dp[i][j]);
            }

    if(dp[nrpers][cantminim]>=cantminim)
        return 1;
    return 0;

}
int cb(int st,int dr)
{
    int mij;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(posibil(mij)==1)
        {
            dr=mij-1;
            tfinal=mij;
        }
        else
            st=mij+1;
    }
    return tfinal;
}
int main()
{
    in>>nrpers>>cantminim;
    for(int i=1; i<=nrpers; i++)
    {
        in>>a[i]>>b[i];
        /*if(a[i]>maxva)
            maxva=a[i];
        if(b[i]>maxvb)
            maxvb=b[i];*/

    }
    //timp_presupus=nrpers*(maxva+maxvb);
    timp_presupus=10000;
    out<<cb(1,timp_presupus)<<'\n';

    return 0;
}