#include <fstream>

using namespace std;
ifstream fin ("rucsac.in");
ofstream fout ("rucsac.out");
int n, gmax, g[5005], p[5005], Dp[2][10004], i, j, l1, l0;
int main()
{
    fin >> n >> gmax;
    for(i=1; i<=n; i++)
        fin >> g[i] >> p[i];
    l0=0;
    l1=1;
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=gmax; j++)
        {
            Dp[l1][j]=Dp[l0][j];
            if(g[i]<=j&&Dp[l0][j-g[i]]+p[i]>Dp[l1][j])
                Dp[l1][j]=Dp[l0][j-g[i]]+p[i];
        }
        swap(l0, l1);
    }
    fout << Dp[l0][gmax];
}