#include <fstream>
#define input "rucsac.in"
#define output "rucsac.out"
using namespace std;
namespace file{
    ifstream f(input);
    ofstream g(output);
    void close(){
        f.close();
        g.close();
    }
}

struct obiect{
    int p;
    int g;
}a[5001];
int c[3][10001];


int main(){
    int n, g, sw=1, prev=2;
    file::f >> n >> g;
    for(int i=1; i<=n; i++)
        file::f >> a[i].g >> a[i].p;
    for(int i=1; i<=g; i++)
        if(a[1].g<=i)
            c[sw][i]=a[1].p;
    for(int i=2;i<=n;i++){
        if(sw==1){
            prev=1;
            sw=2;
        }
        else{
            prev=2;
            sw=1;
        }
        for(int j=1;j<=g;j++){
            if(j - a[i].g >= 0)
                c[sw][j]=( c[prev][j] < (c[prev][j-a[i].g]+a[i].p)  ? (c[prev][j-a[i].g] + a[i].p) : c[prev][j] );
            else{
                if(a[i].g <= j)
                    c[sw][j]=(c[prev][j] < a[i].p ? a[i].p : c[prev][j]);
                else
                    c[sw][j]=c[prev][j];
            }
        }
    }
    file::g<<c[sw][g];
    file::close();
    return 0;
}