#include <bits/stdc++.h>

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

int n, m, w[5001], v[5001], dp[5001][10001];
int main(){
    f>>n>>m;
    for(int i=1; i<=n; ++i)
        f>>w[i]>>v[i];
    for(int i=1; i<=n; ++i)
        for(int j=0; j<=m; ++j){
            dp[i][j]=dp[i-1][j];
            if(j >= w[i] && dp[i][j] < dp[i-1][j-w[i]]+v[i])
                dp[i][j] = dp[i-1][j-w[i]]+v[i];
        }
    g<<dp[n][m]<<'\n';
    return 0;
}