#include <bits/stdc++.h>

using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
//vector<vector<int>>dp;
vector<vector<long long>> dp;

struct rucsac
{
    long long p, g;
};
rucsac v[5001];
void rezolvare(int n,int g)
{
    int i, j;
    dp[0][0] = 0;
    for(i = 1; i <= n; i++)
        for(j = 0; j <= g; j++)
        {
            dp[i][j] = dp[i - 1][j];
            if(j >= v[i].g)
                dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i].g] + v[i].p);
        }
}
int main()
{

    int n,g;
    fin >> n >> g;
    dp.resize(n + 1, vector<long long>(g + 1, 0));
    for(int i =1 ; i <= n; i++)
    {
        fin >> v[i].g >> v[i].p;
    }
    rezolvare(n, g);
            fout << dp[n][g] <<' ';
     //for(int i =1 ; i <= n; i++)
         //   fout << v[i].p <<' ' << v[i].g << '\n';
    return 0;
}