#include <bits/stdc++.h>
using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
int profit1[10001],profit2[10001], greut[5001], pro[5001];
int main()
{
    int n, g, maxim = 0, i, j;
    in >> n >> g;
    for(i = 1; i <= n; i++)
        in >> greut[i] >> pro[i];
    for(i = 1; i <= n; i++) {
        for(j = greut[i]; j <= g; j++) {
            profit1[j] = max(profit2[j], profit2[j - greut[i]] + pro[i]);
            if(i == n)
                maxim = max(maxim, profit1[j]);
        }
        for(j = 1; j <= g; j++) {
           profit2[j] = profit1[j];
        }
    }
    out << maxim;
    return 0;
}