#include <bits/stdc++.h>

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

int n,g,p[5005][10005],i,val,gr,j;

void afis_mat(int linii, int coloane)
{
    int i,j;
    for(i=1;i<=linii;i++){
        for(j=1;j<=coloane;j++)
            fout<<p[i][j]<<' ';
        fout<<'\n';
    }
    fout<<'\n';
}

int main()
{
    fin>>n>>g;
    //afis_mat(n,g);
    fin>>gr>>val;
    p[1][gr]=val;
    for(i=2; i<=n; i++)
    {
        fin>>gr>>val;
        if(val>p[i-1][gr])
            p[i][gr]=val;
        for(j=1; j<=g; j++)
        {
            if(p[i-1][j-gr] != 0)
                p[i][j]=max(p[i-1][j],val+p[i-1][j-gr]);
            else{
                if(p[i][j] < p[i-1][j])
                    p[i][j]=p[i-1][j];
            }
        }
        //afis_mat(n,g);
    }
    fout<<p[n][g];
    return 0;
}