#include <bits/stdc++.h>
using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
int profit[5001][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 = 1; j <= g; j++) {
            profit[i][j] = profit[i - 1][j];
            if(j >= greut[i])
                profit[i][j] = max(profit[i][j], profit[i - 1][j - greut[i]] + pro[i]);
            if(i == n)
                maxim = max(maxim, profit[i][j]);
        }
    }
    out << maxim;
    return 0;
}