#include <iostream>
#include<fstream>
#include <vector>

using namespace std;

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

int rucs(vector<int>& p, vector<int>& w,int n,int g)
{
    vector<vector<int>> d(n+1, vector<int>(g+1, 0));
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= g; j ++)
        {
            if(w[i-1] <= j)
                d[i][j] = max(d[i-1][j], d[i-1][j - w[i-1]] + p[i-1]);
            else
                d[i][j] = d[i-1][j];
        }
    }
    return d[n][g];
}

int main()
{
    int n, g;
    fin >> n >> g;
    vector<int> p(n), w(n);
    for(int i = 0 ; i < n; i ++)
    {
        fin >> w[i] >> p[i];
    }
    fout << rucs(p, w, n, g);
    return 0;
}