#include <bits/stdc++.h>

using namespace std;

int n,v[5005],w[5005],g,dp[2][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[1][j]=dp[0][j];
            else dp[1][j]=max(dp[0][j],dp[0][j-w[i]]+v[i]);
        }
        for(int j=1;j<=g;j++){
            dp[0][j]=dp[1][j];
        }
    }
    out << dp[0][g];

}