#include <bits/stdc++.h>

using namespace std;

const int INF=(int)(1e9);

const int MAXN=(int)(5*1e3+1);

const int MAXG=(int)(1e4+1);

vector<int> previous(MAXG, 0);

vector<int> curr(MAXG, 0);

int main()
{
    freopen("rucsac.in", "r", stdin);
    freopen("rucsac.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,g,w,p;
    cin>>n>>g;
    for (int j=0;j<n;j++){
        cin>>w>>p;
        for (int i=0;i<=g;i++){
            curr[i]=0;
        }
        for (int i=0;i<=g;i++){
            if (i-w>=0){
                curr[i]=max(curr[i], previous[i-w]+p);
            }
            curr[i]=max(curr[i], previous[i]);
        }
        previous=curr;
    }
    cout<<previous[g];
    return 0;
}