#include <iostream>
#include <fstream>
#include <climits>
#define NMAX 5010
using namespace std;
int wt[NMAX],cost[NMAX],n,W;
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){
    long a[2][2*NMAX];
    for(int i=1;i<=n;i++){
        for(int w=0;w<=W;w++){
            if(i==0 || w == 0)  a[i % 2][w] =0;
            else if(w < wt[i-1])  a[i % 2][w] =a[(i+1)%2][w];
            else a[i%2][w] = max(a[(i+1)%2][w],a[(i+1)%2][w-wt[i-1]]+cost[i-1]);
        }
    }
    return a[i%2][W];
}
//wt - weight vectir cost - price vector



int main()
{

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