#include <bits/stdc++.h>

using namespace std;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

#define NMAX 5005
#define GMAX 10005

int i,G,n,curr,dp[2][GMAX],g[NMAX],p[NMAX];

int main()
{
    fin>>n>>G;

    for(int i=1 ; i<=n ; i++)
        fin>>g[i]>>p[i];

    for(int i=1 ; i<=n ; i++)
    {
        curr=i%2;
        for(int j=0 ; j<=G ; j++)
            if(j-g[i]>=0)
                dp[curr][j]=max(dp[1-curr][j],dp[1-curr][j-g[i]]+p[i]);
            else dp[curr][j]=dp[1-curr][j];
    }

    fout<<dp[n%2][G];
    return 0;
}