#include <bits/stdc++.h>

using namespace std;

int n,v[5005],w[5005],g,dp[5005][10005];

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

int main(){
    in >> n >> g;
    for(int i=1;i<=n;i++) in >> w[i] >> v[i];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=g;j++){
            if(w[i]>j) dp[i][j]=dp[i-1][j];
            else dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
        }
    }
    out << dp[n][g];

}