#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("energii.in");
ofstream fout("energii.out");

int g,sc,se,w,a[1001],b[1001],c[5001],d[5001],i,j,mx;

int main()
{
    fin>>g>>w;
    for(i=1;i<=g;i++){
        fin>>a[i]>>b[i];
        sc+=b[i];
        se+=a[i];
    }


    for(i=1;i<=g;i++){
        for(j=1;j<=se-w;j++)
            if(c[j]!=0 && j+a[i]<=se-w)
                d[j+a[i]]=c[j]+b[i];
            else if(j==a[i])
                d[j]=b[i];

        for(j=1;j<=se-w;j++)
            c[j]=max(c[j],d[j]);
    }

    for(i=1;i<=se-w;i++)
        if(c[i]>mx)mx=c[i];

    fout<<sc-mx;

    fin.close();
    fout.close();
    return 0;
}