#include<bits/stdc++.h>
using namespace std;

ifstream f("rucsac.in");
ofstream g("rucsac.out");

int n,we;
int w[5001];
int p[5001];
int dp[2][10001];

int main()
{
    f>>n>>we;
    int i,j;
    int line=0;
    for(i=1;i<=n;++i)
    {
        f>>w[i]>>p[i];
    }
    for(i=1;i<=n;++i)
    {
        for(j=0;j<=we;++j)
        {
            dp[line^1][j]=dp[line][j];
            if(w[i]<=j)
                 dp[line^1][j]=max(dp[line^1][j] , dp[line][j-w[i]]+p[i])  ;
        }
        line=line^1;
    }
    g<<dp[line][we];

	return 0;
}