#include <fstream>
using namespace std;
ifstream f("rucsac.in");
ofstream fout("rucsac.out");
struct gigi{ long long greutate ;long long profit;} v[10000];
long long i , b[10000];
int main()
{
    int n , g ;
    long maxx=0;
    f>>n>>g;
    for(i=1;i<=n;i++)
    {
        f>>v[i].greutate>>v[i].profit;
    }
    for(i=1;i<=n;i++)

    {
        for(int  j=g ;j>=0;j--)
         {
         if(j-v[i].greutate)
        {
            if(b[j-v[i].greutate] && b[j-v[i].greutate]+v[i].profit>b[j])
                {b[j]=b[j-v[i].greutate]+v[i].profit;

            }

        }
        else
        {

            b[j]=v[i].profit;
        }

         }
    }
    maxx=b[1];
    for(i=1;i<=g;i++)
        if(b[i]>maxx) maxx=b[i];
    fout<<maxx;

}