#include <iostream>
#include <iomanip>
#include <fstream>

using namespace std;

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

const int NLIM = 5000 + 10;
const int GLIM = 1e4 + 10;

int n, W;

int val[NLIM];
int wt[NLIM];
int K[NLIM][GLIM];


int main()
{
    fin >> n >> W;
    for( int i = 0; i < n; ++i )
    {
        fin >> wt[i] >> val[i];
    }

	int i, w;
    // Build table K[][] in bottom up manner
    for (i = 0; i <= n; i++)
    {
        for (w = 0; w <= W; w++)
        {
            if (i==0 || w==0)
                K[i][w] = 0;
            else if (wt[i-1] <= w)
                    K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]);
            else
                    K[i][w] = K[i-1][w];

           // cout << setw( 3 ) <<  K[i][w] << " ";
        }
        //cout << "\n";
    }

    fout << K[n][W] << "\n";



	return 0;
}