#include<fstream>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int N,G,w[5001],v[5001],dp[5001][10001];
int main()
{
    f>>N>>G;
    for(int i=1;i<=N;++i)f>>w[i]>>v[i];
    for(int i=1;i<=N;++i)
        for(int j=0;j<=G;++j){
            dp[i][j]=dp[i-1][j];
            if(w[i]<=j)
                dp[i][j]=max(dp[i][j],dp[i-1][j-w[i]]+v[i]);
        }
    g<<dp[N][G];
    return 0;
}