#include <bits/stdc++.h>
#define nmax 5001
#define gmax 10001
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int g[gmax],c[nmax],n,G,dp[2][gmax];
void Citire()
{
    int i;
    fin>>n>>G;
    for(i=1;i<=n;i++)
        fin>>g[i]>>c[i];
}
void Rezolvare()
{
    int i,j,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;
    }
    int sol=-1;
    for(i=1;i<=G;i++)
        sol=max(sol,dp[L0][i]);
    fout<<sol<<"\n";
}
int main()
{
    Citire();
    Rezolvare();
    return 0;
}