#include <bits/stdc++.h>

using namespace std;

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

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

int w[MAXN], p[MAXN];

vector<int> previous(MAXG);

vector<int> curr(MAXG);

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