#include<bits/stdc++.h>
using namespace std;
ifstream fin("rucsac.in");ofstream fout("rucsac.out");
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];
}

long int i,j;long int k[5001][10001];
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]=max(v[i-1]+k[i-1][j-w[i-1]],k[i-1][j]);

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

    }
}

fout<<k[n][g];
return 0;
}