//#include <iostream>
#include <bits/stdc++.h>
using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
const int Max=10005;
int n,g,w[Max],p[Max],mat[2][Max];

void citire()
{
    in>>n>>g;
    for(int i=1;i<=n;i++)
    {
        in>>w[i]; in>>p[i];
    }
}
void sol()
{
   for(int i=1;i<=n;i++)
   {
        swap(mat[1],mat[0]);
       for(int G=1;G<=g;G++)
   {
       mat[1][G]=mat[0][G];
      if(w[i]<=G)
        if(mat[1][G]<mat[0][G-w[i]]+p[i])
           mat[1][G]=mat[0][G-w[i]]+p[i];
   }

   }
   out<<mat[1][g];



}
int main()
{
   citire();
   sol();
    return 0;
}