#include <fstream>
#define Max_Size 5010
#define Max_Size_DP 10090
using namespace std;

ifstream f("rucsac.in"); ofstream g("rucsac.out");

int N, G;
int W[Max_Size], P[Max_Size];
int DP[Max_Size_DP * 2];

inline void read_Data() {
    f >> N >> G;

    for(int i = 1; i <= N; ++i) f >> W[i] >> P[i];
}

inline void solve() {
    DP[0] = 1;
    int sol = 0;
    for(int i = 1; i <= N; ++i)
        for(int j = G; j >= 0; --j)
            if(DP[j] + P[i] > DP[j + W[i]])
                DP[j + W[i]] = DP[j] + P[i];

    for(int i = 1; i <= G; ++i)
        if(DP[i] > sol) sol = DP[i];

    g << sol - 1<< '\n';
}

int main() {

    read_Data();

    solve();

    g.close();
    return 0;
}