#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

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

int N, G, val[10005], greu[10005], profit[5005], sol = -1;

int main()
{
    fin>>N>>G;
    for(int i=1; i<=N; i++)
        fin>>greu[i]>>val[i];

    for(int i=1; i<= N; i++)
        for(int gp = G - greu[i]; gp >= 0; gp--)
            if(profit[gp + greu[i]] < profit[gp] + val[i]){
                    profit[gp + greu[i]] = profit[gp] + val[i];
                    if(sol < profit[gp + greu[i]])
                        sol = profit[gp + greu[i]];
            }

    fout<<sol;
    return 0;
}