#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 n;
int G;

vector< pair<int,int> > v;

void read_data()
{
    in >> n >> G;

    int i;

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


}



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 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();
    solve();
    //print_data();
    out<<dp[n-1][G];

}