#include <fstream>
using namespace std;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

int n,nr, sol,i,j,lp,lc;
int g[5001], p[5001];
int dp[3][10001];

int main()
{
    fin>>n>>nr;
    for(i=1;i<=n;++i)
        fin>>g[i]>>p[i];


        lc=1;
        lp=2;


        for(i=1;i<=n;i++)
        {


        for(j=0;j<=nr;++j)
        {

            dp[lc][j]=dp[lp][j];


            if(g[i]<=j)
             dp[lc][j] = max(dp[lc][j], dp[lp][j-g[i]] +p[i]);

        }

        swap(lc, lp);
        }


   fout<<dp[lp][nr];
}