#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;
    f >> n >> G;
    vector<int> w(n+ 1);
    vector<int> p(n+ 1);
    int DP[n+1][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 || j == 0)
                DP[i][j] = 0;
            else if (j - w[i] >= 0 && DP[i-1][j] < DP[i-1][j-w[i]] + p[i])
            {
                DP[i][j] = DP[i-1][j-w[i]] + p[i];
            }
            else
                DP[i][j] = DP[i-1][j];
        }
    }
    g << DP[n][G];
    return 0;
}