#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int n,g,wt[10001],v[10001];
int knapsack(int n, int g, int wt[], int v[])
{   int k[n+1][g+1];
    for(int i=0;i<=n;i++)
    {   for(int w=0;w<=g;w++)
        {   if(w==0||i==0) k[i][w]=0;
            else if(wt[i-1]<=w)
                    k[i][w]=max(v[i-1]+k[i-1][w-wt[i-1]],k[i-1][w]);
                 else
                    k[i][w]=k[i-1][w];
        }
    }
    return k[n][g];
}
int main()
{
    fin>>n>>g;
    for(int i=0;i<n;i++) fin>>wt[i]>>v[i];
    fout<<knapsack(n,g,wt,v);
    return 0;
}