#include<fstream>
using namespace std;
ifstream fin ("rucsac.in");
ofstream fout ("rucsac.out");
int n,G,a[10010],b[10010],i,j,k;
pair<int,int> v[5010];
#define x first
#define y second

int main()
{
    fin>>n>>G;
    for(i=1;i<=n;i++)
    {
        fin>>v[i].x>>v[i].y;
        for(j=1;j<=G;j++)
        {
            if(j-v[i].x>=0)
                a[j]=max(b[j],b[j-v[i].x]+v[i].y);
            else
                a[j]=b[j];
        }
        swap(a,b);
    }
    fout<<b[G];
    fin.close();
    fout.close();
    return 0;
}