#include <fstream>

using namespace std;
const int nmax=5005;
struct obj
{
    int w,p;
} v[nmax];
int dp[2][2*nmax];
int main()
{
    ifstream cin("rucsac.in");
    ofstream cout("rucsac.out");
    int n,w;
    cin>>n>>w;
    for(int i=1; i<=n; i++)
        cin>>v[i].w>>v[i].p;
    for(int i=1; i<=n; i++)
    {
        for(int j=0; j<=w; j++)
            if(j>=v[i].w)
                dp[1][j]=max(dp[0][j],dp[0][j-v[i].w]+v[i].p);
            else
                dp[1][j]=dp[0][j];
        for(int j=0; j<=w; j++)
            dp[0][j]=dp[1][j];
    }
    cout<<dp[0][w];
    return 0;
}