#include <iostream>
#include <fstream>

using namespace std;

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

const int nmax = 10010;
const int gmax = 5010;

int dp[2][gmax], weight[nmax], profit[nmax], W, n;

int main()
{
    fin >> n >> W;
    for (int i = 1; i <= n; i++)
        fin >> weight[i] >> profit[i];

    int linie = 0; /// suntem ori pe linia 0 ori pe linia 1

    for(int i = 1;i <= n;i++) /// iteram prin obiecte
    {
        for(int j = 1;j <= W;j++) /// iteram prin costurile posibile
            {
                dp[1 - linie][j] = dp[linie][j];///nu punem obiectul i

                if(weight[i] <= j) /// daca poti sa folosesti obiectul
                {
                    dp[1 - linie][j] = max(dp[linie][j],profit[i] + dp[linie][j - weight[i]]);///max(a folosi obiectul i sau a nu folosi obiectul i);
                }
            }
        linie == 1 ? linie = 0 : linie = 1;
    }   
    fout<<dp[linie][W];
}