#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

const int MAXN = 5010;
const int MAXG = 10010;
int main() {
    ifstream f("rucsac.in");
    ofstream g("rucsac.out");
    int n, G, current, ant;
    f >> n >> G;
    vector<int> w(n+ 1);
    vector<int> p(n+ 1);
    int DP[3][G+1];
    for (int i = 1 ;i <= n; i++)
    {
        f >> w[i] >> p[i];
    }
    for(int i = 0; i<= n; i++)
    {
        for(int j = 0; j <= G; j++)
        {
            if(i == 0) {
                DP[i][j] = 0;
                continue;
            }
             current = i %2;
             ant = (i+1) %2;
             if (j - w[i] >= 0 && DP[ant][j] < DP[ant][j-w[i]] + p[i])
             {
                DP[current][j] = DP[ant][j-w[i]] + p[i];
             }
             else
                DP[current][j] = DP[ant][j];
        }
    }
    g << DP[current][G];
    return 0;
}