#include <bits/stdc++.h>
#define up(n) for(int (i)=1;(i)<=(n);(i)++)
#define dn(n) for(int (i)=n;(i)>=1  ;(i)--)
#define get(n) scanf("%d",&(n))
#define put(n) printf("%d",n)
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define vit vector<int>::iterator
using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
int GMax, CMax[10001], S,n,q,k, i, g[10001], c[10001], Uz[10001][10001];
int main()
{
    in>>n>>GMax;
    for(i=1;i<=n;i++) in>>g[i]>>c[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;
                }
    out<<CMax[GMax];
    return 0;
}