#include<fstream>
#include<algorithm>

using namespace std;

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

pair <int, int> V[1003],D[5003];
int W,G,Sol=10000000;

int main()
{
    fin>>G>>W;
    for(int i=1;i<=G;i++)
        fin>>V[i].first>>V[i].second;
    sort(V+1,V+1+G);
    D[0].first=1;
    for(int i=1;i<=G;i++)
    {
        for(int j=W;j>=0;j--)
            if(D[j].first==1)
        {
            if(j+V[i].first>=W)
                Sol=min(Sol,D[j].second+V[i].second);
            else
            {
                D[j+V[i].first].first=1;
                if(D[j+V[i].first].second==0)
                    D[j+V[i].first].second=D[j].second+V[i].second;
                else
                    D[j+V[i].first].second=max(V[i].second+D[j].second,D[j+V[i].first].second);
            }
        }
    }
    fout<<Sol<<'\n';
}