#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;
    }
    for(int i=0; i<2; i++)
        for(int j=0; j<=g; j++)
            dp[i][j]=INT_MIN;
    dp[1][v[1].greutate]=v[1].profit;
    int linie=0;
    for(int i=2; i<=n; i++)
    {
        for(int j=0; j<=g; j++)
        {
            dp[linie][j]=dp[1-linie][j];
            if(v[i].greutate<=j)
            {
                dp[linie][j]=max(dp[linie][j],dp[1-linie][j-v[i].greutate]+v[i].profit);
            }
        }
        linie=1-linie;
    }
    linie=1-linie;
    for(int i=1; i<=g; i++)
    {
        fin=max(fin,dp[linie][i]);
    }
    out<<fin;
    return 0;
}