#include <iostream>
#include<fstream>

using namespace std;

int n,greutate, v[5073],g[5073],last[10073],best[10073], rasp=0;


void problem()
{
    for (int i=0;i<n;i++)
        for (int j=greutate-g[i];j>=0;j--)
            {
                best[j+g[j]]=max(best[j+g[j]], v[i]+best[j]);
                if (best[j+g[j]]>rasp)
                    rasp=best[j+g[j]];
                last[j+g[i]]=i;
            }
}






int main()
{
   ifstream in("rucsac.in");

   in>>n>>greutate;

   for (int i=0;i<n;i++)
      {
          in>>v[i]>>g[i];
      }
    problem();

   ofstream out("rucsac.out");
   out<<rasp;

   return 0;
}