#include <bits/stdc++.h>
#define nmax 5005
#define mmax 10002
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int g[nmax],c[nmax],n,G,dp[2][mmax];
/// dp[i][j]-costul maxim obtinut din primele i obiecte obtinandu-se greutatea j
void Citire()
{
    int i;
    fin>>n>>G;
    for(i=1;i<=n;i++)
        fin>>g[i]>>c[i];
}
void Dp()
{
    int i,j,sol=0,L0,L1;
    dp[0][g[1]]=c[1];
    L0=0;
    L1=1;
    for(i=2;i<=n;i++)
    {
        for(j=1;j<=G;j++)
            if(j>=g[i])
              dp[L1][j]=max(dp[L0][j],dp[L0][j-g[i]]+c[i]);
        else dp[L1][j]=dp[L0][j];
        L0=1-L0;
        L1=1-L1;
    }
    for(j=1;j<=G;j++)
        sol=max(sol,dp[L0][j]);
    fout<<sol<<"\n";
}
int main()
{
    Citire();
    Dp();
    fin.close();
    fout.close();
    return 0;
}