#include <fstream>

using namespace std;

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

const int MAXN = 5002;
const int MAXG = 10002;
int n, g;
int w[MAXN], p[MAXN];
int d[2][MAXG];

int main()
{
    cin >> n >> g;
    for(int i=1; i<=n; i++)
        cin >> w[i] >> p[i];
    
    for(int i=1; i<=n; i++) {
        for(int j=1; j<w[i]; j++)
            d[i%2][j] = d[(i-1)%2][j];
        for(int j=w[i]; j<=g; j++)
            d[i%2][j] = max(d[(i-1)%2][j], d[(i-1)%2][j-w[i]]+p[i]);
    }
    
    cout << d[n%2][g];

    return 0;
}