#include <fstream>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int main()
{
    int n,g,p[5005],w[5005];
    int dp[2][10005];
    fin >> n >> g;
    for (int i=1;i<=n;i++)
    {
        fin >> w[i] >> p[i];
    }
    for (int i=1;i<=g;i++)
    {
        if (w[1]>i) dp[0][i]=0;
        else dp[0][i]=p[1];
    }
    for (int j=2;j<=n;j++)
    {
        for (int i=1;i<=g;i++)
        {
            if (w[j]>i) dp[1][i]=dp[0][i];
            else dp[1][i]=max(dp[0][i],p[j]+dp[0][i-w[j]]);
        }
        for (int i=1;i<=g;i++)
        {
            dp[0][i]=dp[1][i];
        }
    }
    fout << dp[1][g];
}