#include <iostream>
#include <fstream>
#include <vector>
#define Nmax 500
#define Gmax 1000
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

vector<pair<int,int>> date(Nmax);
int n,G;
int d[Nmax][Gmax];
void Citire ()
{
    fin>>n>>G;
    for (int i=1;i<=n;i++)
        {int greutate,profit;
            fin>>greutate>>profit; // first e valoarea si second e greutatea
            date[i].first = profit;
            date[i].second = greutate;
        }
}
/*
d[i][j] = profitul maxim selectand din primele i elemente, cu greutate maxima j;
d[i][j] = min (d[i-1][j],d[i-1][j-greutate[i]) */
void Dinamica()
{
    int dim = date.size();
    for (int j=1;j<=G;j++)
        for (int i=0; i<dim; i++){
          if (i==0 && date[i].second <=j ) d[i][j]= date[i].first;
           else if (date[i].second <= j ) d[i][j] = max (d[i-1][j],date[i].first + d[i-1][j-date[i].second]);
            else if (date[i].second > j) d[i][j]= d[i-1][j];
        }

   fout<<d[dim-1][G];
}
int main()
{
    Citire();
    Dinamica();
    return 0;
}