#include <iostream>
#include<fstream>
#include<vector>


using namespace std;

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


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

bool cmp(pair<int,int> & p1 , pair<int,int> & p2)
{
    double r1 = double(p1.second) / double(p1.first);
    double r2 = double(p2.second) / double(p2.first);
    return r1 < r2;
}

double problem1()
{
    vector<pair<int , int> > vect;

    for(int i =0;i<n;i++)
    {
        vect.push_back(make_pair(g[i],v[i]));
    }

    make_heap(vect.begin() , vect.end() , cmp);
    for (int i = 0;i<n;i++)
    cout << vect[i].first << " " << vect[i].second << "\n";
    cout << "----\n";
    int gr_curent = greutate;
    double valoarea_curenta = 0;

    pair <int , int> element = (*vect.begin());
    pop_heap(vect.begin() , vect.end() , cmp);
    vect.pop_back();


    while (element.first < gr_curent)
    {
        cout << element.first << " " << element.second << "\n";
        gr_curent -= element.first;
        valoarea_curenta += element.second;
        if(!vect.empty())
        {
            element = (*vect.begin());
            pop_heap(vect.begin() , vect.end() , cmp);
            vect.pop_back();
        }
        else
        {
            return valoarea_curenta;
        }
    }
    if (gr_curent > 0)
    {
        valoarea_curenta += double(element.second) * (double(gr_curent) / double(element.first));
    }
    return valoarea_curenta;
}

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

   in>>n>>greutate;

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

   return 0;
}