#include<bits/stdc++.h>
#define N 5001
#define G 10001
using namespace std;

int n,gm,g[N+1],c[N+1],viz[G+1][N+1],C[G+1];

void read();
void solve();
void print();

int main()
{
    read();
    solve();
    print();

}

void read()
{
    freopen("rucsac.in","r",stdin);
    scanf("%d%d",&n,&gm);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&g[i],&c[i]);
}

void solve()
{
    int i,j,s;
    //C[0]=0;
    for(i=1;i<=gm;i++) C[i]=-1;

    for(s=1;s<=gm;s++)
        for(i=1;i<=n;i++)
          if( g[i]<=s && C[s-g[i]]!=-1   &&  !viz[s-g[i]][i] )
            if(C[s]<C[s-g[i]]+c[i])
    {
        C[s]=C[s-g[i]]+c[i];
        for(j=1;j<=n;j++)
            viz[s][j]=viz[s-g[i]][j];
        viz[s][i]=1;
    }

}

void print()
{
    freopen("rucsac.out","w",stdout);
    printf("%d\n",C[gm]);
    //for(int i=1;i<=n;i++)
   //     if(viz[gm][i]==1) printf("%d ",i);
}