#include <bits/stdc++.h>

using namespace std;

ifstream f("rucsac.in");
ofstream g("rucsac.out");

int Castig[50][50], Alege[50][50], Gr[100], C[100],i,j,n,G,Obiect;

int main()
{
    f>>n;
    f>>G;
    for(i = 1; i <= n; i++)
    {
        f>>Gr[i];
        f>>C[i];
    }
    for(i = 1; i <= n; i ++)
        for(j = 1; j <= G; j++)
            if(Gr[i] <= j)
                if(C[i] + Castig[i-1][j-Gr[i]] > Castig[i-1][j])
                {
                    Castig[i][j] = C[i] + Castig[i-1][j-Gr[i]];
                    Alege[i][j] = i;
                }
                else
                {
                    Castig[i][j] = Castig[i-1][j];
                    Alege[i][j] = Alege[i-1][j];
                }
            else
            {
                Castig[i][j] = Castig[i-1][j];
                Alege[i][j] = Alege[i-1][j];
            }
    i = n; j = G;
    g<<Castig[i][j]<<"\n";
    /*
    while(Alege[i][j])
    {
        Obiect = Alege[i][j];
        g<<"Produsul "<<Alege[i][j]<<" Greutate "<<Gr[Alege[i][j]]<<" Castig "<<C[Alege[i][j]]<<"\n";
        while(Obiect == Alege[i][j])
        {
            j -= Alege[i][j];
            i--;
        }
    } */

    return 0;
}