#include <fstream>

using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
 int gmax , n , i , v[1001] , a[1001] , vmax[1001][10001],g;

int main()
{
    fin>>n>>gmax;
 for(i=1;i<=n;i++)
     fin>>a[i]>>v[i];
 for(i=1;i<=n;i++)
    for(g=1;g<=gmax;g++)
 { vmax[i][g]=vmax[i-1][g];
   if(a[i]<=g&&v[i]+vmax[i-1][g-a[i]]>vmax[i][g])
       vmax[i][g]=v[i]+vmax[i-1][g-a[i]];

 }
 fout<<vmax[n][gmax];

}