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