#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
int n, A[5001][10001], G;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
int k = 1;
pair<int, int> V[5001];
int main()
{
    in >> n >> G;
    for(int i = 1; i <= n; i++) {
        in >> V[i].first >> V[i].second;
    }
    for(int i = 0; i <= G; i++) {
        if(V[1].first <= i) A[1][i] = V[1].second;
    }
    for(int i = 1; i <=n; i++) {
        for(int j = 0; j <= G; j++) {
            //if(j==0) A[i][j] = 0;
            if(V[i].first <= j) {
                A[i][j] = max(A[i-1][j], A[i-1][j-V[i].first] + V[i].second);
            } else {
                A[i][j] = A[i-1][j];
            }
        }
    }

    out << A[n][G];

    return 0;
}