#include <iostream>
#include <cstdio>
using namespace std;

const int MAXG=10005;

int N,G,W,P,maxUsed,ret;
int dp[MAXG];

int main () {
    freopen ("rucsac.in","r",stdin);
    freopen ("rucsac.out","w",stdout);

    cin>>N>>G;
    for (int i=1; i<=N; ++i) {

        cin>>W>>P; maxUsed+=W;
        for (int i=min (G,maxUsed); i>=W; --i)
            ret=max (ret,dp[i]=max (dp[i],dp[i-W]+P));
    }
    cout<<ret;

    return 0;
}