#include <bits/stdc++.h>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
vector<vector<long long>> dp;
struct rucsac
{
    long long p, g;
};
rucsac v[5001];
void rezolvare(long long n,long long g)
{
    int i, j;
    dp[0][0] = 0;
    for(i = 1; i <= n; i++)
        for(j = g; j >= v[i].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] <<' ';

    return 0;
}