#include <bits/stdc++.h>

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

int n,m,nr,G;
int w[5001];
int val[5001];
int dp1[10005],dp2[10005];
int main()
{
    //ios_base::sync_with_stdio(0);
    //f.tie(0);
    //g.tie(0);
    int i,j,k,z;
    f>>n>>G;
    for(i=1;i<=n;i++)
    {
        f>>w[i];
        f>>val[i];
    }
    //dp1 ->linia i-1
    //dp2 ->linia i (curenta)
    for(i=1;i<=n;i++)
    {
        for(j=0;j<=G;j++)
        {
            dp2[j]=dp1[j];
            if(j>=w[i])// and dp2[j]<val[i]+dp1[j-w[i]])//ca sa nu fie dp[][-1],dp1[-1]
            {
                //dp2[j]=val[i]+dp1[j-w[i]];
                dp2[j]=max(dp2[j],val[i]+dp1[j-w[i]]);
            }
            //dp[i][j]=dp[i-1][j];
           // if(j>=w[i])
            //    dp[i][j]=max(dp[i][j],val[i]+dp[i-1][j-w[i]]);

        }
        swap(dp1,dp2);
    }
    //dp[i][j]=profit maxim in primele i-1 nr si greutatea maxima j
    g<<dp1[G];

    return 0;
}