#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[2][10001];
void dp(){
    int l = 0;
    for(int i = 1; i<=n; i++, l = 1-l){

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

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


    dp();



    return 0;
}