#include <bits/stdc++.h>

using namespace std;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

struct obiect
{
    int cost, greu;
}o[5001];

int v[10001];
int n, g, maxi, vmax;

int main()
{
    fin>>n>>g;
    for(int i=1; i<=n; i++)
        fin>>o[i].greu>>o[i].cost;
    for(int i=1; i<=n; i++)
    {
        for(int j=vmax; j>=1; j--)
        {
            if(v[j]!=0)
                if(j+o[i].greu<=g)
                    if(v[j+o[i].greu]<v[j]+o[i].cost)
                    {
                        v[j+o[i].greu]=v[j]+o[i].cost;
                        if(vmax<j+o[i].greu)
                            vmax=j+o[i].greu;
                        if(maxi<v[j+o[i].greu])
                            maxi=v[j+o[i].greu];
                    }
        }
        if(v[o[i].greu]<o[i].cost)
           v[o[i].greu]=o[i].cost;
        if(o[i].greu>vmax)
            vmax=o[i].greu;
    }
    fout<<maxi;
    return 0;
}