#include <fstream>
using namespace std;

int n, G, g[5001], p[5001], pmax = 0, dp[5001][5001], SOL;

int main()
{
    ifstream fin("rucsac.in");
    ofstream fout("rucsac.out");
    int i,j;

    fin>>n>>G;
    for(i=1;i<=n;i++)
        fin>>g[i]>>p[i];


    SOL=0;
    for(i = 1;i<=n;i++)
        for(j=0;j<=G;++j)
        {
            int var1=0, var2=0;
            var1 = dp[i-1][j];

            if(j-g[i] >= 0)
                var2 = p[i] + dp[i-1][ j-g[i] ];

            dp[i][j] = max(var1,var2);
            if(i==n)
                SOL = max(SOL, dp[i][j]);
        }
    fout<<SOL<<"\n";
    fout.close();
    return 0;
}