#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

const string filename = "rucsac";
ifstream fin(filename + ".in");
ofstream fout(filename + ".out");

int n, g, d[10005], dp[10005], ans;

int main()
{
    fin >> n >> g;
    for(int w, p, i = 1; i <= n; i++)
    {
        fin >> w >> p;
        for(int j = 0; j <= g; j++)
        {
            d[j] = dp[j];
            if(j >= w)
                d[j] = max(d[j], dp[j - w] + p);
        }
        for(int j = 0; j <= g; j++)
            dp[j] = d[j];
    }
    for(int i = 0; i <= g; i++)
        ans = max(ans, dp[i]);
    fout << ans << '\n';
    return 0;
}