#include <fstream>
#define MAX 10001
using namespace std;

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

int n, g, w[MAX], p[MAX], dp[MAX];

int main()
{
    int i, j, best = 0;
    in >> n >> g;

    for(i = 1; i <= n; i++) in >> w[i] >> p[i];

    for(i = 1; i <= n; i++)
    {
        for(j = g; j > w[i]; j--)
            if((dp[j-w[i]] + p[i] > dp[j]) && dp[j-w[i]] != 0) dp[j]=dp[j-w[i]]+p[i];

        if(dp[w[i]] < p[i]) dp[w[i]]=p[i];
    }

    for(i = 1; i <= g; i++)
        if(dp[i] > best) best = dp[i];

    out << best;

    return 0;
}