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

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

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;
    for(i=1;i<=gm;i++) C[i]=-1;

    for(s=1;s<=gm;s++)
        for(i=1;i<=n;i++)
          if(!viz[s-g[i]][i] && C[s-g[i]]+c[i]>C[s] && C[s-g[i]]!=-1 && g[i]<=s)
    {
        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);*/
}