//#include <iostream>
#include <bits/stdc++.h>
using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
const int Max=10005;
int viz[Max][Max],n,g,w[Max],p[Max],profit[Max];
void citire()
{
    in>>n>>g;
    for(int i=1;i<=n;i++)
    {
        in>>w[i]; in>>p[i];
    }
}
void sol()
{
    int q;
    for(int G=1;G<=g;G++)
    {
        for(int i=1;i<=n;i++)
          if(w[i]<=G && !viz[G-w[i]][i])
        {
          if(profit[G-w[i]]+p[i]>profit[G])
          {
              profit[G]=profit[G-w[i]]+p[i];
              for(int k=1;k<=n;k++)
                viz[G][k]=viz[G-w[i]][k];
              viz[G][i]=1;
          }
        }



    }

out<<profit[g];

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