#include <iostream>
#include <fstream>
#include <climits>
#define NMAX 5010
using namespace std;
int wt[NMAX],cost[NMAX],n,W;
long a[NMAX][2*NMAX];
ifstream f("rucsac.in");
ofstream g("rucsac.out");
void citeste(){
    f >> n >> W;
    for(int i=0;i<n;i++){
        f >> wt[i] >> cost[i];
    }
}

long profit(int i,int W){
        if(i == 0 || W == 0)   a[i][W] = 0;
        else if(a[i][W] < LLONG_MAX)    return a[i][W];
        else if(W >= wt[i-1])    a[i][W] = max(profit(i-1,W),cost[i-1] + profit(i-1,W-wt[i-1]));
        else a[i][W] =  profit(i-1,W);
        return a[i][W];
}



int main()
{

    citeste();
    for(int i=0;i<=n;i++)
        for(int j=0;j<=W;j++)
            a[i][j]=LLONG_MAX;
    g << profit(n,W);
    return 0;
}