#include <bits/stdc++.h>
#define NM 5005
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int w[NM],p[NM],dp[2][NM*2];
int main()
{   int n,gMax,sol=0;
    f>>n>>gMax;
    for(int i=1; i<=n; i++) f>>w[i]>>p[i];
    for(int i=1; i<=n; i++)
    {   for(int j=0; j<=gMax; j++)
        {   dp[1][j]=dp[0][j];
            if(w[i]<=j)
                dp[1][j]=max(dp[0][j],dp[0][j-w[i]]+p[i]);
            sol=max(sol,dp[1][j]);
        }
        for(int j=0; j<=gMax; j++) dp[0][j]=dp[1][j];
    }
    g<<sol;
    return 0;
}