#include <fstream>
using namespace std;

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

const short N_Max = 5003, M_Max = 10003;

short N, G, P[N_Max], W[N_Max], Dp[N_Max][M_Max];

inline short max(short a, short b) {
    return a > b ? a : b;
}

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

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

inline void solve() {
    for(short i = 1; i <= N; ++i)
        for(short cw = 1; cw <= G; ++cw) {
            Dp[i][cw] = Dp[i - 1][cw];

            if(W[i] <= cw)
                Dp[i][cw] = max(Dp[i][cw], Dp[i - 1][cw - W[i]] + P[i]);
        }
}

int main()  {
    read_Data();
    solve();

    g << Dp[N][G] << '\n';

    g.close();
    return 0;
}