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


int t[11000][2];
    //int d[150001];
int mat[2][150001];
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;
    }
int c,r;
c=0;
r=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=g;j++)
        {
             mat[r][j]=mat[c][j];
             if(j>=t[i][0])
            mat[r][j]=max(mat[c][j-t[i][0]]+t[i][1],mat[r][j]);



        }

        int aux=r;
        r=c;
        c=aux;
    }


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