#include <fstream>
#include <iostream>
#define nmax 5010
#define maxg 10010
int n,gmax;
int c[nmax],g[nmax];
int cmax[maxg],uz[maxg][nmax];
using namespace std;
void citire();
void rezolvare();
void afisare();

int main(){
    citire();
    rezolvare();
    afisare();
    return 0;
}

void citire()
{
    ifstream in("rucsac.in");
    int i,j;
    in >>n>>gmax;
    for(i=1;i<=n;i++)in>>g[i]>>c[i];
    in.close();
}
void rezolvare()
{
int s,k,i;
for(s=1;s<=gmax;s++)cmax[s]=-1
for(s=1;s<=gmax;s++)
    for(i=1;i<=n;i++)
    if(g[i]<=s && cmax[s-g[i]]!=-1 && !uz[s-g[i]][i])
        if(cmax[s]<c[i]+cmax[s-g[i]])
        {
            cmax[s]=c[i]+cmax[s-g[i]];
            for(k=1;k<=n;k++)
            uz[s][k]=uz[s-g[i]][k];
            uz[s][i]=1;
        }
}
void afisare()
{
    ofstream out("rucsac.out");
    out<<cmax[gmax]<<endl;
    out.close();
}