#include <bits/stdc++.h>
using namespace std;
//d[i][j] = castigul maxim pe care il pot obtine din primele i obiecte avand greutatea j
//(g[i], v[i])
//2 optiuni: sa pun sau sa nu pun obiectul in rucsac
//d[i][j] = max(d[i - 1][j], d[i - 1][j - g[i]] + v[i])
const int NMAX = 5e3;
const int GMAX = 1e4;

int g[NMAX + 1], v[NMAX + 1];
int d[NMAX + 1][GMAX + 1];

//6 10
//3 7
//3 4
//1 2
//1 9
//2 4
//1 5
int main() {
    ifstream cin("rucsac.in");
    ofstream cout("rucsac.out");
    int n, G;
    cin >> n >> G;
    for(int i = 1; i <= n; i++) {
        cin >> g[i] >> v[i];
    }
    for(int i = 1; i <= n; i++) {

        for(int j = 1; j <= G; j++) {
            if(j < g[i]) {
                d[i][j] = d[i - 1][j];

            } else {
                d[i][j] = max(d[i - 1][j], d[i - 1][j - g[i]] + v[i]);
            }
        }
    }
    int sol = 0;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= G; j++) {
            sol = max(sol, d[i][j]);
        }

    }
    cout << sol;
    return 0;
}