#include <fstream>
#include <vector>
#include <string.h>
using namespace std;
struct obiect{
    int val,gr;
};
int N,G; vector<int> m[10050]; int s[10050]; obiect obiecte[5050];
bool inSet(int k, int l){
    for (int i=0; i<m[l].size(); i++)
        if (m[l][i]==k) return true;
    return false;
}
int main(){
    ifstream in("rucsac.in");
    ofstream out("rucsac.out");
    in >> N >> G;
    int i,j;
    for (i=1; i<=N; i++)
        in >> obiecte[i].gr >> obiecte[i].val;

    memset(s,0,sizeof(s));
    memset(m,0,sizeof(m));
    s[0]=0;

    for (i=1; i<=G; i++){
        for (j=1; j<=N; j++)
            if (obiecte[j].gr<=i && obiecte[j].val+s[i-obiecte[j].gr]>s[i])
                if (!inSet(j,i-obiecte[j].gr)){
                    s[i]=obiecte[j].val+s[i-obiecte[j].gr];
                    m[i]=m[i-obiecte[j].gr];
                    m[i].push_back(j);
                }
    }
    out << s[G];
}