#include <iostream>
#include <fstream>
#include <vector>
#define gmax 10005
#define nmax 5005
using namespace std;

int n, gr;
int prof_max[gmax];
int W[nmax], P[nmax];
int in_rucs[gmax][nmax];

void read()
{
    ifstream f("rucsac.in");
    f >> n >> gr;
    for(int i=1; i<=n; ++i)
    {
        f >> W[i] >> P[i];
    }
    f.close();
}

void solve()
{
    for(int i=1; i<=gmax; ++i) prof_max[i]=-1;
    for(int s=1; s<=gmax; ++s)
    {
        for(int i=1; i<=n; ++i)
        {
            if(W[i]<=s && prof_max[s-W[i]]!=-1 && !in_rucs[s-W[i]][i])
            {
                if(prof_max[s] < P[i] + prof_max[s-W[i]])
                {
                    prof_max[s] = P[i] + prof_max[s-W[i]];
                    for(int k=1; k<=n; ++k)
                        in_rucs[s][k]=in_rucs[s-W[i]][k];
                    in_rucs[s][i]=1;
                }
            }
        }
    }
}

void out()
{
    ofstream g("rucsac.out");
    g << prof_max[gr] << '\n';
    g.close();
}

int main()
{
    read();
    solve();
    out();
    return 0;
}