#include <bits/stdc++.h>
using namespace std;

const int NMAX = 5e3;
const int GMAX = 1e4;
const int INF = 0x3F3F3F3F;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

int n,g;
int G[NMAX + 1], P[NMAX + 1];
int m[2][GMAX + 1];

void initializare(){
    for(int i = 1;i<=n;++i)
        for(int j = 1;j<=g;++j)
            m[i][j] = INF;
}

/*int rucsac(int i, int g){ /// recursiv, fara sa fie asa eficient;
    if(i == 0)
        return 0;
    if(m[i][g] != INF)
        return m[i][g];
    int skip_obj = rucsac(i - 1, g);
    int get_obj = 0;
    if(G[i] <= g)
        get_obj = P[i] + rucsac(i - 1, g - G[i]);
    int ans = max(get_obj, skip_obj);
    m[i][g] = ans;
    return m[i][g];
}*/

void rucsac(){
    for(int i = 1;i<=n;++i){
        int paritate = i % 2;
        for(int gc = 0;gc <= g;++gc){
            m[paritate][gc] = m[1 - paritate][gc];
            if(G[i] <= gc)
                m[paritate][gc] = max(m[paritate][gc], P[i] + m[1 - paritate][gc - G[i]]);
        }
    }
     fout << m[n % 2][g];
}

int main(){

    fin >> n >> g;
    for(int i = 1;i<=n;++i)
        fin >> G[i] >> P[i];
    ///initializare();
    ///fout << rucsac(n,g);
    rucsac();
    return 0;
}