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

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




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

int i,j;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(){
int n,g;fin>>n>>g;int v[n];int w[n];
for(int a=0;a<n;a++){
    fin>>w[a]>>v[a];
}

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







return 0;
}