#include<bits/stdc++.h>
using namespace std;
ifstream fin("rucsac.in");ofstream fout("rucsac.out");

long int maxi(long int a,long int b) { return (a > b)? a : b; }




long int rucsac(long int g,long int n,long int*v,long int*w){

long int i,j;long int k[n+1][g+1];
for(i=0;i<=n;i++){
    for(j=0;j<=g;j++){

        if(i==0||j==0){k[i][j]=0;}

        else if(w[i-1]<=j) {k[i][j]=maxi(v[i-1]+k[i-1][j-w[i-1]],k[i-1][j]);}

        else {k[i][j]=k[i-1][j];}

    }
}



return k[n][g];
}


int main(){
long int n,g;fin>>n>>g;long int v[n];long int w[n];
for(long int a=0;a<n;a++){
    fin>>w[a]>>v[a];
}

fout<<rucsac(g,n,v,w);







return 0;
}