#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
pair<int,int> a[5005];
int dp[5005][10005];
int main(){
    int n,w,i,m=0,j;
    in>>n>>w;
    for(i=1; i<=n; ++i)
        in>>a[i].f>>a[i].s;
    for(i=1; i<=n; ++i){
        for(j=0; j<=w; ++j){
            dp[i][j]=dp[i-1][j];
            if(j>=a[i].f)
                dp[i][j]=max(dp[i][j], dp[i-1][j-a[i].f]+a[i].s);
        }
    }
    out<<dp[n][w];
    return 0;
}