#include <bits/stdc++.h>
#define nmax 5001
#define gmax 10001

using namespace std;

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

int dp[nmax][gmax],n,G,g[nmax],v[nmax];

int main()
{
    int i,j;
    fin >> n >> G;
    for(i = 1; i <= n; i++)
        fin >> g[i] >> v[i];

    for(i = 1; i <= n; i++)
        for(j = 1; j <= G; j++)
            if(g[i] > j) dp[i][j] = dp[i-1][j];
            else dp[i][j] = max(dp[i-1][j],dp[i-1][j-g[i]]+v[i]);

    fout << dp[n][G] << "\n";

    fin.close();
    fout.close();
    return 0;
}