#include<bits/stdc++.h>
using namespace std;
const int NMAX=5001;
const int GMAX=10002;
int dp[NMAX][GMAX],n,val[NMAX],wg[NMAX],w;
int main()
{
    //dp[i][j] cost maxim din primele i elemente, si care au greutatea fix j
    // d[i][j]=d[i-1][j]-nu il iau pe elementul i
    //d[i][j]=v[i]+d[i-1][j-wg[i]]
    freopen("rucsac.in","r",stdin);
    freopen("rucsac.out","w",stdout);
    cin>>n>>w;
    for(int i=1;i<=n;i++)
    {
        cin>>wg[i]>>val[i];
    }
    dp[0][0]=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=w;j++)
        {
            dp[i][j]=dp[i-1][j];
            if (j-wg[i]>=0)
                dp[i][j]=max(dp[i][j],val[i]+dp[i-1][j-wg[i]]);
        }
    }
    int maxx=0;
    for (int j=0;j<=w;j++)
    {
        maxx=max(maxx,dp[n][j]);
    }
    cout<<maxx;
    return 0;
}