#include <stdio.h>
#include <iostream>

using namespace std;

const int nmax = 5005;
const int gmax = 10010;
int Best[2][gmax], W[nmax], P[nmax], N, G;

/// Best[i][cw] = max profit using first i objects having at most cw weight
void solve() {
    int i, cw, sw = 0;
    for(i = 1; i <= N; i++, sw = 1 - sw)
        for(cw = 1; cw <= G; cw++){
            Best[sw][cw] = Best[1 - sw][cw];
            if(cw - W[i] >= 0 && Best[sw][cw] < Best[1 - sw][cw - W[i]] + P[i])
                Best[sw][cw] = Best[1 - sw][cw - W[i]] + P[i];
        }
    cout << Best[1 - sw][G];
}

int main()
{
    freopen ("rucsac.in", "r", stdin);
    freopen ("rucsac.out", "w", stdout);

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

    solve();

    return 0;
}