#include <iostream>
#include <fstream>
#include <vector>
#include <utility>


using namespace std;

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

const int NMAX =  10000 + 5;
//int dp[5001][NMAX];
int dp[NMAX];
int n;
int G;
int sol;

vector< pair<int,int> > v;

void read_data()
{
    int i;

    in >> n >> G;

    for( i = 0 ; i < n ; ++i)
    {
        pair<int,int> tmp;
        in>>tmp.first>>tmp.second;
        v.push_back(tmp);
    }
}


/*O(N^2) complexitate timp  / O(N*G) complexitate memorie
void solve()
{
    pair<int,int>a;
    for(int i = 0 ; i <n; ++i)
    {
        for(int j = 1 ;  j<=G ; ++j)
        {
            if(i-1<0)
            {
                if(j-v[i].first>=0)
                {
                    dp[i][j]=v[i].second;
                }
            }
            else
            {
                if(j-v[i].first>=0)
                    dp[i][j] = max(dp[i-1][j-v[i].first]+v[i].second,dp[i-1][j]);
                else
                    dp[i][j]=dp[i-1][j];
            }
        }
    }





}


*/
void optim_solve() // O(N^2) complexitate timp // O(N) complexitate spatiu
{
    int i,j;

    for(i= 0 ; i < n ; ++i)
    {
        for(j=G-v[i].first; j>=0; --j)
        {
            if(dp[j+v[i].first] < dp[j]+v[i].second)
                dp[j+v[i].first] = dp[j]+v[i].second;

            if(dp[j+v[i].first] > sol)
                sol = dp[j+v[i].first];


        }

    }





}


/*
void print_data()
{
    for(int i = 0 ; i<n; ++i)
    {
        for(int j = 1 ; j<=G; ++j)
            out<<dp[i][j]<<' ';

        out<<'\n';
    }

}
*/


int main()
{
    read_data();
    optim_solve();
    //solve();
    //print_data();
    out<<sol;

}