#include<fstream>
#include<vector>
using namespace std;
#define maxn 5002
#define maxg 10003
ifstream f("rucsac.in");
ofstream g("rucsac.out");
unsigned int n,G;
struct pereche{
    int gr,pr;
};
vector <int> l1,l2;

pereche P[maxn];
int main(){
    f>>n>>G;
    for(int i=1;i<=n;++i){
            f>>P[i].gr>>P[i].pr;

    }
    l1.push_back(0);
    for(int i=1;i<=G;++i)
        if(i==P[1].gr)
            l1.push_back(P[1].pr);
        else
            l1.push_back(max(0,l1[i-1]));
    l2.push_back(0);

    for(int i=2;i<=n;++i){
        l2.resize(0);

        l2.push_back(0);
        for(int j=1;j<=G;++j)
            if(j-P[i].gr>=0)
                l2.push_back(max(l1[j], l1[j-P[i].gr]+P[i].pr));
            else
                l2.push_back(l1[j]);
        l1=l2;


    }
    g<<l2[G];
    return 0;
}