#include <bits/stdc++.h>

using namespace std;
ifstream in ("rucsac.in");
ofstream out ("rucsac.out");
const int NMAX=5005,GMAX=10005;
int n,g;
struct pereche
{
    int greutate,profit;
} v[NMAX];
int dp[2][GMAX];
int fin;
int main()
{
    in>>n>>g;
    for(int i=1; i<=n; i++)
    {

        in>>v[i].greutate>>v[i].profit;
    }
    int linie=0;
    for(int i=1; i<=n; i++,linie=1-linie)
    {
        for(int j=0; j<=g; j++)
        {
            dp[1-linie][j]=dp[linie][j];
            if(v[i].greutate<=j)
            {
                dp[1-linie][j]=max(dp[1-linie][j],dp[linie][j-v[i].greutate]+v[i].profit);
            }
        }
    }
    for(int i=1; i<=g; i++)
    {
        fin=max(fin,dp[linie][i]);
    }
    out<<fin;
    return 0;
}