#include<fstream>
using namespace std;
int N,G,i,g,p,greutate[5009],pret[5009],Y,x,MAX,dif,suma;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int main ()
{
    fin>>N>>G;
    for(i=1;i<=N;i++)
    {
        fin>>g>>p;
        greutate[i]=g;
        pret[i]=p;
    }
    do
    {
        Y=G;
        MAX=0;
        for(i=1;i<=N;i++)
        {
            if(greutate[i]<=G)
            {
            dif=pret[i]-greutate[i];
            }
            if(dif>MAX)
            {
                x=i;
                MAX=dif;
            }
        }
        G=G-greutate[x];
        suma=suma+pret[x];
        greutate[x]=0;
        pret[x]=-1;
    }
    while(Y!=G);
    suma=suma+1;
    fout<<suma;
    fin.close();
    fout.close();
    return 0;
}