#include <fstream>
#include <algorithm>
using namespace std;
int n,wmax,nmax;
int i,cap;
int p[5010],w[5010];
int dp[5010][10010];
ifstream cin("rucsac.in");
ofstream cout("rucsac.out");
int main()
{
    cin>>n>>wmax;
    for(i=1;i<=n;i++)
    {
        cin>>w[i]>>p[i];
    }
    for(i=1;i<=n;i++)
    {
        for(cap=0;cap<=wmax;cap++)
        {
            //dp[0][cap]=0;
            //if(cap-w[i]<0)
            dp[i][cap]=dp[i-1][cap];
            if(cap-w[i]>=0)
            {
                dp[i][cap]=max(dp[i-1][cap],dp[i-1][cap-w[i]]+p[i]);
                nmax=dp[i][cap];
            }
        }
    }
    nmax=dp[n][wmax];
    cout<<nmax;
    return 0;
}