#include <fstream>
using namespace std;
ifstream cin("rucsac.in");
ofstream cout("rucsac.out");
int i, j, n, m, l, G;
int D[2][10002], w[5002], p[5002];
int main() {
    cin>>n>>G;
    for(i=1;i<=n;i++){
        cin>>w[i]>>p[i];
    }
    l=0;
    /// d[i][j]= profitul maxim pe care il putem obtine pana la pozitia i, avand greutatea j
    /// l-linie anterioara, 1-l - linie curenta
    for(i=1;i<=n;i++,l=1-l){
        for(j=0;j<=G;j++){
            D[1-l][j]=D[l][j]; /// nu adaugam obiectul i
            if(w[i]<=j){
                D[1-l][j]=max(D[1-l][j], D[l][j-w[i]]+p[i]); ///adaugam obiectul i la o solutie anterioara
            }

        }
    }
    /// solutie: d[n][G], adica d[l][G]
    cout<<D[l][G];

}