#include <iostream>
#include <fstream>

using namespace std;

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

int n,g,contor;
int rucsac[10001],cost[5001],profit[5001];
int main()
{
    in>>n>>g;
    for(int i=1;i<=n;++i)
        in>>cost[i]>>profit[i];
    for(int i=1;i<=n;++i)
    {
        for(int j=g;j>=cost[i];--j)
            rucsac[j]=max(rucsac[j-cost[i]]+profit[i],rucsac[j]);
    }
    out<<rucsac[g];
    return 0;
}