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

using namespace std;

const int nmax = 5005;
const int gmax = 10010;
int Best[nmax][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;
    for(i = 1; i <= N; i++)
        for(cw = 1; cw <= G; cw++){
            Best[i][cw] = Best[i - 1][cw];
            if(cw - W[i] >= 0 && Best[i][cw] < Best[i - 1][cw - W[i]] + P[i])
                Best[i][cw] = Best[i - 1][cw - W[i]] + P[i];
        }
    cout << Best[N][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;
}