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


int t[11000][2];
    //int d[150001];
int mat[10000][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(mat[i-1][j-t[i][0]]+t[i][1],mat[i-1][j]);



        }
    }


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