#include <bits/stdc++.h>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
struct obiect
{
    int g;
    int p;
};
obiect v[5001];
int sol[2][10001];
int main()
{
    int i,n,k,j;
    fin>>n>>k;
    for(i=1; i<=n; i++)
    {
        fin>>v[i].g;
        fin>>v[i].p;
    }
    for(i=1; i<n; i++)
        for(j=i+1; j<=n; j++)
            if(v[i].g>v[j].g)swap(v[i],v[j]);
    for(i=1; i<=n; i++)
        for(j=1; j<=k; j++)
        {
            if(i%2==0)
            {
                if(j<v[i].g)sol[0][j]=sol[1][j];
                else sol[0][j]=max(sol[1][j],sol[1][j-v[i].g]+v[i].p);
            }
            else
            {
                if(j<v[i].g)sol[1][j]=sol[0][j];
                else sol[1][j]=max(sol[0][j],sol[0][j-v[i].g]+v[i].p);
            }
        }
    int s=0;
    if(n%2==1)
    {
         for(i=1;i<=k;i++)
            if(s<sol[1][i])s=sol[1][i];
    }
    else
    {
         for(i=1;i<=k;i++)
            if(s<sol[0][i])s=sol[0][i];
    }
    fout<<s;
}