#include <iostream>
#define nmax 10001
using namespace std;
int n,G,C[nmax][nmax];
struct obiect
{
    int g;
    int c;
};
obiect a[nmax];
void citire()
{
    int i;
    cin>>n>>G;
    for(i=1;i<=n;i++)
        cin>>a[i].g>>a[i].c;
}
void dinamica()
{
    int i,j;
    for(i=0;i<=G;i++)C[0][i]=0;
    for(j=0;j<=n;j++)C[j][0]=0;
    for(i=1;i<=n;i++)
        for(j=1;j<=G;j++)
            if(a[i].g>j)C[i][j]=C[i-1][j];
            else C[i][j]=max(C[i-1][j],a[i].c+C[i-1][j-a[i].g]);
    cout<<C[n][G]<<" ";
}
void solutie()
{
    int x,y;
    x=n;
    y=G;
    while(C[x][y]!=0)
        if(C[x][y]!=C[x-1][y])
            {
                //cout<<x<<" ";
                y=y-a[x].g;
                x--;
            }
        else x--;
}
int main()
{
    citire();
    dinamica();
    solutie();
    return 0;
}