#include <fstream>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int n,g,p[5001],gr[5001],mat[5001][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][j] = max(mat[i - 1][j], p[i] + mat[i - 1][j - gr[i]]);
            }
            else{
                mat[i][j]=mat[i - 1][j];
            }
        }
    }
    fout<<mat[n][g];
    return 0;
}