#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 pv1[GLIM], pv2[GLIM];
int* v1 = pv1;
int* v2 = pv2;


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 = 1; i <= n; i++)
    {
        for (w = 1; w <= W; w++)
        {
            if (wt[i-1] <= w)
                    v2[w] = max(val[i-1] + v1[w-wt[i-1]], v1[w]);
            else
                    v2[w] = v1[w];

            //cout << setw( 3 ) <<  v2[w] << " ";
        }
        //cout << "\n";
        int* emp = v1;
        v1 = v2;
        v2 = emp;
    }

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



	return 0;
}