#include <fstream>
#include <vector>

std::ifstream f("rucsac.in");
std::ofstream g("rucsac.out");

int n,capacity;
std::vector<int>wt,val;
int dp[2][10001];

void read(){

    f >> n >> capacity;

    wt.resize(n + 1);
    val.resize(n + 1);

    for(int i = 1;i <= n;i++)
        f >> wt[i] >> val[i];
}

void precalc(){

    for(int i = 1;i <= n;i++){
        int index = (i % 2 == 0 ? 0 : 1);
        for(int j = 1;j <= capacity;j++){
            if(index == 0){
                if(j < wt[i])
                    dp[0][j] = dp[1][j];
                else
                    dp[0][j] = std::max(dp[1][j],dp[1][j - wt[i]] + val[i]);
            }else{
                if(j < wt[i])
                    dp[1][j] = dp[0][j];
                else
                    dp[1][j] = std::max(dp[0][j],dp[0][j - wt[i]] + val[i]);
            }
        }
    }
}

void print(){
    if(n % 2 == 0)
        g << dp[0][capacity];
    else
        g << dp[1][capacity];
}

int main(){

    read();
    precalc();
    print();

    return 0;
}