#include<fstream>
using namespace std;

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

const int Nmax = 5002;
const int Gmax = 10003;

int n,g,i,j,dp[2][Gmax],a[Nmax],b[Nmax];


int main()
{
    cin>>n>>g;
    for (i=1;i<=n;i++) cin >> a[i] >> b[i];
    for (i=1;i<=n;i++){

        for (j=1;j<=g;j++)
             {
                 dp[1][j]=dp[0][j];
                 if (j>=a[i]) dp[1][j] = max(dp[1][j],dp[0][j-a[i]]+b[i]);
             }
        for (j=1;j<=g;j++)
         dp[0][j]=dp[1][j];

    }

    cout << dp[1][g];
    return 0;
}