#include <iostream>
#include <fstream>

using namespace std;

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

int w[5005], p[5005], dp[10005];

int main()
{
    int n, g;

    fin >> n >> g;

    for(int i = 1; i <= n; i++)
    {
        fin >> w[i] >> p[i];
    }

    int maxx = 0;

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

    fout << maxx;

}