#include <bits/stdc++.h>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int n, g;
int p[5001], v[5001];
int d[5001][10001];
void dp(){
    for(int i = 1; i<=n; i++){

        for(int j = 1; j<=g; j++){
            if(j>=p[i]){
                d[i][j] = max(d[i-1][j], d[i-1][j-p[i]] + v[i]);
            } else {
                d[i][j] = d[i-1][j];
            }
        }
    }

}

int main(){
    fin >>n>>g;
    for(int i = 1; i<=n; i++){
        fin >>p[i]>>v[i];
    }


    dp();
    fout << d[n][g];


    return 0;
}