/*
  Lefter Sergiu - 26/01/2023
*/
#include <fstream>

using namespace std;

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

const int N = 5000;

struct obiect {
    int g, v;
};

obiect a[N+1];
int n, G, d[2*N + 1];

int main() {
    in >> n >> G;
    for (int i = 1; i <= n; ++i) {
        in >> a[i].g >> a[i].v;
    }
    d[0] = 0;
    int sol = 0;
    for (int i = 1; i <= n; i++)
        for (int j = G - a[i].g; j >= 0; --j)
        {
            if(d[j + a[i].g] < d[j] + a[i].v)
            {
                d[j + a[i].g] = d[j] + a[i].v;
                if (d[j + a[i].g] > sol)
                    sol = d[j + a[i].g];
            }
        }
    out << sol;
    in.close();
    out.close();
    return 0;
}