#include <iostream>
#include <fstream>
#include <vector>
#define NMAX 5001
#define GMAX 10001

int c[NMAX],g[NMAX],uz[GMAX][NMAX],cmax[NMAX],n,gmax;
using namespace std;

int main()
{
    ifstream in("rucsac.in");
    ofstream out("rucsac.out");
    in >> n >> gmax;

    for(int i=1;i<=n;i++)
        in >> g[i] >> c[i];

    for(int i=1;i<=n;i++)
        cmax[i]=-1;

    for(int S=1;S<=gmax;S++)
    {
        for(int i=1;i<=n;i++)
        {
            if(g[i]<=S && cmax[S-g[i]]!=-1 && uz[S-g[i]][i]==0)
                if(cmax[S]<c[i]+cmax[S-g[i]])
            {
                cmax[S]= c[i] + cmax[S-g[i]];
                for(int k=1;k<=n;k++)
                    uz[S][k] = uz[S-g[i]][k];
                uz[S][i]=1;
            }
        }
    }
    out << cmax[gmax];
    return 0;
}