#include<bits/stdc++.h>

using namespace std;

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

int n,g,W[5100],P[5100],A[5100][10100];

int main(){
    in >> n >> g;
    for (int i=1; i<=n; i++){
        in >> W[i] >> P[i];
    }
    for (int i=1; i<=n; i++){
        for (int j=0; j<=g; j++){ //?
            if (W[j]<=j)
                A[i][j] = max(A[i-1][j], A[i-1][j-W[i]] + P[i]);
            else A[i][j] = A[i-1][j];
        }
    }
    out << A[n][g];
    return 0;
}