#include <iostream>
#include <fstream>
using namespace std;


short t[5000][2];
    //int d[150001];
short mat[5000][10000];
ifstream f("rucsac.in");
ofstream h("rucsac.out");
int main()
{
     int n,g;
    f>>n;
    f>>g;
    for(int i=1;i<=n;i++)
    {
        //mat[0][i]=-1;
        int j,k;
        f>>j;
        f>>k;
        t[i][0]=j;
        t[i][1]=k;
    }

    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=g;j++)
        {
             mat[i][j]=mat[i-1][j];
             if(j>=t[i][0])
            mat[i][j]=max((int)mat[i-1][j-t[i][0]]+t[i][1],(int)mat[i-1][j]);



        }
    }


    h<<mat[n][g]<<"  ";
    //h<<d[g];
   return 0;
}