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

using namespace std;

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

struct Ob{
    int w;
    int p;
};

int n, g;

vector<Ob> a;
int dp[10005];

int main()
{
    fin >> n >> g;
    a.resize(n);
    for(int i = 0; i < n; i++)
        fin >> a[i].w >> a[i].p;

    for(int i = 0; i < n; i++)
        for(int j = g; j >= 1; j--)
            if(a[i].w <= j)
                dp[j] = max(dp[j], dp[j-a[i].w]+a[i].p);
    int sol = 0;
    for(int i = 0; i <= g; i++)
        sol = max(sol, dp[i]);

    fout << sol;
    return 0;
}