#include <fstream>
#include <vector>
#include <iostream>
using namespace std;

int main(){
    ifstream ifs("rucsac.in");
    ofstream ofs("rucsac.out");

    int N,G;
    ifs>>N>>G;

    vector<vector<int> > o(2,vector<int>(N+1));//[0]=Weight,[1]=Price

    for(int i=1;i<=N;i++)
        ifs>>o[0][i]>>o[1][i];

    vector<vector<int> > d(2,vector<int>(G+1,0));

    int rs=0; //row select

    for(int i=1;i<=N;i++){ // first <i> objects...
        for(int j=1;j<=G;j++){//...with weight smaller than <j>
            d[rs][j]=d[1-rs][j];

            if(j-o[0][i]>=0){
                int t=d[1-rs][j-o[0][i]]+o[1][i];
                if(t>d[rs][j])
                    d[rs][j]=t;
            }
        }
        rs=1-rs;// 0,1,0,1 ...
    }
    ofs<<d[1-rs][G]<<"\n";
}