#include <bits/stdc++.h>
using namespace std;
#define int long long
ifstream f("rucsac.in");
ofstream g("rucsac.out");
#define cin f
#define cout g
int dp[5005],i,j,n,G;
struct per{
    int w;
    int v;
}a[5005];
signed main()
{
    cin>>n>>G;
    for(i=1;i<=n;i++){
        cin>>a[i].w>>a[i].v;
    }
    for(i=1;i<=n;i++){
        for(j=G;j>=a[i].w;j--){
            dp[j]=max(dp[j],dp[j-a[i].w]+a[i].v);
        }
    }
    cout<<dp[G];
    return 0;
}