#include <iostream>
#include <fstream>
using namespace std;

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

const int maxWeight = 10009;
const int maxN = 5005;

int dp[maxWeight][maxN];
int weight[maxN];
int value[maxN];
int n;
int w;

void solveKnapsack(){
    for(int i = 1; i <= w; ++i){
        for(int j = 1; j <= n; ++j){
            if( i - weight[j] >= 0)
                dp[i][j] = max( dp[i][j-1], value[j] + dp[ i - weight[j]][ j-1 ] );
            else dp[i][j] = dp[i][j-1];
        }
    }
    fout  << dp[w][n] << "\n";
    /*int i = w;
    int j = n;
    while(i > 0 && j > 0){
        if( dp[i][j] != dp[i][j-1] ){
            fout << "Object " << j << " was used\n";
            i -= weight[j];
            j--;
        }
        else{
            j--;
        }
    }*/
}

void read(){
    fin >> n >> w;
    for(int i = 1; i <= n; ++i)
        fin >> weight[i] >> value[i];
}

int main()
{
    read();
    solveKnapsack();
    return 0;
}