#include <iostream>
#include <fstream>
using namespace std;
//int main(){
//
//    int N,G,i,j;
//    ifstream f("rucsac.in");
//    ofstream g("rucsac.out");
//    f>>N>>G;
//    int a[100][100];
//    int w[100],p[100];
//
//    for(i=1;i<=N;i++){
//        f>>w[i]>>p[i];
//    }
//    for(i=0;i<=N;i++){
//        for(j=0;j<=G;j++){
//            if(i==0||j==0){
//                a[i][j]=0;
//            }
//            else{
//                if(j-w[i]<0){
//                    a[i][j]=a[i-1][j];
//                }
//                else{
//                    a[i][j]=max(a[i-1][j],a[i-1][j-w[i]]+p[i]);
//                }
//            }
//        }
//    }
//
//    for(i=0;i<=N;i++){
//        for(j=0;j<=G;j++){
//            cout<<a[i][j]<<" ";
//        }
//        cout<<endl;
//    }
//    return 0;
//}


int main(){

    int N,G,i,j;
    ifstream f("rucsac.in");
    ofstream g("rucsac.out");
    f>>N>>G;
    int a[10001],s,w[5001],p[5001];
    s=0;
    //a[0]=0;

    for(i=0;i<=G;i++){
       a[i]=0;

    }
    for(i=1;i<=N;i++){
        f>>w[i]>>p[i];

    }
    for(i=1;i<=N;i++){
        for(j=G-w[i];j>=0;j--){
            if(a[j+w[i]]<a[j]+p[i]){
                a[j+w[i]]=a[j]+p[i];
                if( a[j+w[i]]>s){
                    s=a[j+w[i]];
                }
            }
        }
    }
    g<<s;
    return 0;
}