#include <fstream>
#include <algorithm>
#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[5001][10001];


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