#include <bits/stdc++.h>
#define N 5001
#define X 10001
using namespace std;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

int cw, p, n, g, a1[X], a2[X], a[N][X];

void citire(){
    fin>>n>>g;
    for(int i = 1; i <= n; ++i)
        fin>>a1[i]>>a2[i];

}

void alg(){
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= g; ++j){
            a[i][j] = a[i-1][j];
            if(a1[i] <= j)
                a[i][j] = max(a[i][j], a[i-1][j-a1[i]] + a2[i]);
        }
    }
}

int main(){
    citire();
    alg();
    fout<<a[n][g];
}