#include <iostream>
#include <fstream>
using namespace std;

int n,C; // n-nr de obiecte; C-capacitatea rucsacului
int greutate[5001],profit[5001];
/* greutate[i]= greutatea obiectului i
   profit[i]= profitul adus de obiectul i
*/
int Solutie[5001][10001];//aici calculez solutia problemei
//Solutie[n][C] = solutia problemei

int maxim(int a,int b)
{
    return a > b ? a : b;
}

int calculeazaSolutieMatrice()
{
    for(int i=1;i<=n;i++)
        for(int j=0;j<=C;j++)
            if(j>=greutate[i])//daca am loc in rucsac pentru obiectul i
            {
                Solutie[i][j] = maxim ( Solutie[i-1][j],Solutie[i-1][j-greutate[i]]+profit[i]);
                /* Solutie[i-1][j] = solutia problemei fara a alege obiectul i
                  Solutie[i-1][j-greutate[i]]+profit[i] = solutia pb din profitul adus de obiectul i(profit[i])
                  si cea mai buna solutie fara greutatea obiectului i( adica Solutie[i-1][j-greutate[i]] )
                */
            }
            else //nu am loc in rucsac
                Solutie[i][j]=Solutie[i-1][j];// adica cea mai buna solutie fara obiectul i

   return Solutie[n][C];
}



int main()
{
    ifstream in("rucsac.in");
    in>>n>>C;
    for(int i=1;i<=n;++i)
        in>>greutate[i]>>profit[i];
    in.close();
    ofstream out("rucsac.out");
    out<<calculeazaSolutieMatrice();
    out.close();
    return 0;
}