#include <fstream>

using namespace std;

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

int n,g;
int w[5005],p[5005];
int d[2][10010];

int main(){
    fin>>n>>g;
    for(int i=1;i<=n;++i) fin>>w[i]>>p[i];
    int c=0;
    for(int i=1;i<=n;++i,c=1-c)
    for(int cw=0;cw<=g;++cw){
        d[c][cw]=d[1-c][cw];
        if(cw>=w[i]){
            d[c][cw]=max(d[1-c][cw],d[1-c][cw-w[i]]+p[i]);
        }
    }
    int sol=d[1-c][g];
    fout<<sol;





    return 0;
}