#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
struct obiect{int w,p;};
vector <obiect> v;
vector <int> v1;
vector <int> v2;
int main()
{
    ifstream f("rucsac.in");
    ofstream g("rucsac.out");
    int n,m,i,x,y,j;
    f>>n>>m;
    for (i=1;i<=n;i++)
    {
        f>>x>>y;
        v.push_back({x,y});
    }
    for (i=1;i<=m;i++) v1.push_back(0);
    for (i=0;i<n;i++)
    {
        if (i%2==0)
        {
            for (j=0;j<=m;j++)
            {
               if(j-v[i].w>=0) v2.push_back(max(v1[j],v1[j-v[i].w]+v[i].p));
               else v2.push_back(v1[j]);
            }
            v1.clear();
        }
        else
        {
            for (j=0;j<=m;j++)
            {
                if (j-v[i].w>=0) v1.push_back(max(v2[j],v2[j-v[i].w]+v[i].p));
                else v1.push_back(v2[j]);
            }
            v2.clear();
        }
    }
    if ((n-1)%2==0) g<<v2[m]<<'\n';
    else g<<v1[m]<<'\n';
    f.close();
    g.close();
    return 0;
}