#include <iostream>
#include <fstream>

#define in short int
#define q  a[i]
#define w  b[i]
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
in n,m,a[5001],b[5001],c[5002][10001];
void citire()
{
    f>>n>>m;
    for(int i=1;i<=n;i++){
        f>>a[i]>>b[i];
    }
    a[n+1]=b[n+1]=0;
}
void afisare()
{
    for(in i=1;i<=n;i++)
    {
        for(in j=1;j<=m;j++)cout<<c[i][j]<<" ";
        cout<<endl;
    }
}
void dinamica ()
{

    for(in i=1;i<=n+1;i++)
    {
        for(in j=1;j<q;j++){c[i][j]=c[i-1][j];
          }
                c[i][q]=w;
                if(c[i-1][q]>c[i][q])c[i][q]=c[i-1][q];
                for(in j=1;j<=m-q;j++){
                    if(w+c[i-1][j]>c[i-1][j+q]&&c[i-1][j]!=0){
                        c[i][j+q]=w+c[i-1][j];
                    }
                     else{
                        c[i][j+q]=c[i-1][j+q];
                     }
                }
    }
 g<<c[n+1][m];
}

int main()
{
    citire();
    dinamica();

    return 0;
}