#include <iostream>
#include <fstream>
#include <climits>
#define NMAX 5000
using namespace std;
long long wt[NMAX],cost[NMAX],n,W;
long long a[NMAX][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 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;
    cout << profit(n,W);
    return 0;
}