#include <bits/stdc++.h>

using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
const int Nmax=5e3+5; //5005
int D[Nmax][Nmax];
int main()
{
    int n,GM,x,value;
    f>>n>>GM;
    for(int i=1; i<=n; i++)
    {
        f>>x>>value;
        for(int j=1;j<=GM;j++){

            if(j>=x)
                D[i][j]= max(D[i-1][j], D[i-1][j-x]+value);
            else
                D[i][j]=D[i-1][j];

        }
    }

        g<<D[n][GM];

    return 0;
}