#include<bits/stdc++.h>

using namespace std;

ifstream fin("rucsac1.in");
ofstream fout("rucsac1.out");

#define NMAX 10005

vector<pair<int,int>> v;
int dp[2][NMAX] ;

int main()
{
    int n,gmax;
    fin>>n>>gmax;
    for(int i=1;i<=n;i++)
    {
        int g,val;
        fin>>g>>val;
        v.push_back({g,val});
    }



    for(int i=0;i<=gmax;i++)
        dp[0][i] = 0;

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=gmax;j++)
        {

            if(v[i-1].first <= j)
            {
                dp[1][j] = max(dp[0][j],dp[0][j-v[i-1].first] + v[i-1].second);
            }
            //cout<<dp[2][j]<< " ";
        }

        for(int j=1;j<=gmax;j++)
        {
            dp[0][j] = dp[1][j];
        }
        //cout<<endl;

    }

    fout<<dp[1][gmax];

}