#include <fstream>

using namespace std;

ifstream cin("rucsac.in");
ofstream cout("rucsac.out");

struct ura
{
    int g,p;
}v[5001];

int dp[2][10001];
int main()
{
    int n,G,i,j;

    cin>>n>>G;
    for(i=1;i<=n;i++)
        cin>>v[i].g>>v[i].p;

    for(i=1;i<=n;i++)
        for(j=1;j<=G;j++)
            if(j-v[i].g>=0)
                dp[i%2][j]=max(dp[(i-1)%2][j],dp[(i-1)%2][j-v[i].g]+v[i].p);
            else
                dp[i%2][j]=dp[(i-1)%2][j];
    cout<<dp[n%2][G];

    return 0;
}