#include <fstream>

using namespace std;
ifstream f("energii.in");
ofstream g("energii.out");
struct el{
    int pr,co;
}v[1003];
el aux;
int a[1003][5003],b[1003][5003];
int main()
{
    int n,w,i,j,au,bu;
    f>>n>>w;
    for(i=1;i<=n;i++)
    {
        f>>v[i].pr>>v[i].co;
        a[i][1]=v[i].pr;
        b[i][1]=v[i].co;
    }
    for(i=1;i<n;i++)
    {
        for(j=i+1;j<=n;j++)
        {
            if(v[i].co>v[j].co)
            {
                aux=v[i];
                v[i]=v[j];
                v[j]=aux;
            }
            else
            {
                if(v[i].co==v[j].co)
                {
                    if(v[i].pr>v[j].pr)
                    {
                        aux=v[i];
                        v[i]=v[j];
                        v[j]=aux;
                    }
                }
            }
        }
    }
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=w;j++)
        {

                if(a[i-1][j-1]+v[i].pr>=j&&(b[i][j]==0||b[i][j]>v[i].co+b[i-1][j-1]))
                {
                    a[i][j]=a[i-1][j-1]+v[i].pr;
                    b[i][j]=b[i-1][j-1]+v[i].co;
                }
                else
                {
                    if(a[i-1][j]>a[i][j-1])
                    {
                    a[i][j]=a[i-1][j];
                    b[i][j]=b[i-1][j];
                    }
                    else
                    {
                        a[i][j]=a[i][j-1];
                        b[i][j]=b[i][j-1];
                    }
                }
                if(b[i][j]>v[i].co&&j<=v[i].pr)
                {
                    b[i][j]=v[i].co;
                    a[i][j]=v[i].pr;
                }
                if(i>1)
                {
                if(b[i-1][j]<b[i][j]&&a[i-1][j]>=j)
                {
                    a[i][j]=a[i-1][j];
                    b[i][j]=b[i-1][j];
                }
                }
                if(j>1)
                {
                    if(b[i][j-1]<b[i][j]&&a[i][j-1]>=j)
                    {
                        a[i][j]=a[i][j-1];
                        b[i][j]=b[i][j-1];
                    }
                }

        }
    }
    g<<b[n][w];
    return 0;
}