#include <fstream>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int n,g,p[5001],gr[5001],mat[2][10001];
int main() {
    fin>>n>>g;
    for(int i=1;i<=n;i++){
        fin>>gr[i]>>p[i];
        for(int j=0;j<=g;j++) {
            if(j-gr[i]>=0) {
                mat[i%2][j] = max(mat[(i - 1)%2][j], p[i] + mat[(i - 1)%2][j - gr[i]]);
            }
            else{
                mat[i%2][j]=mat[(i - 1)%2][j];
            }
        }
    }
    fout<<mat[n%2][g];
    return 0;
}