#include <bits/stdc++.h>
using namespace std;
int n, g, D[2][11000], G[6000], P[6000];
int u = 1;
int main(){
    ifstream cin("rucsac.in");
    ofstream cout("rucsac.out");
    cin >> n >> g;
    for(int i=1; i<=n; i++){
        cin >> G[i] >> P[i];
    }

    for(int i=1; i<=n; i++){
        for(int j=1; j<=g; j++){
            if(j - G[i] >= 0){
                D[u][j] = max(D[!u][j], (D[!u][j-G[i]] + P[i]));
            } else {
                D[u][j] = D[!u][j];
            }
        }
        u = !u;
    }

    cout << D[!u][g] << endl;
}