#include <bits/stdc++.h>
using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
int dp[2][10001];
int main(){
    int n,w,i,m=0,j,x,y;
    bool b=0;
    in>>n>>w;
    for(i=1; i<=n; ++i, b=!b){
        in>>x>>y;
        for(j=0; j<=w; ++j){
            dp[b][j]=dp[!b][j];
            if(j>=x)
                dp[b][j]=max(dp[b][j], dp[!b][j-x]+y);
        }
    }
    out<<dp[!b][w];
    return 0;
}