#include <fstream>
using namespace std;
 
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
 
const int maxn=5005, maxg=10005;
 
int L1[maxg],L2[maxg],W[maxn],P[maxn];
int i,cw,N,G;
 
int main() {
    fin >> N >> G;
    for(i=1;i<=N;i++) fin >> W[i] >> P[i];
    for(i=1;i<=N;i++) {
        for(cw=0;cw<=G;cw++) {
            if(cw-W[i]<0) L2[cw]=L1[cw];
            else L2[cw]=max(L1[cw],L1[cw-W[i]]+P[i]);
        }
        memcpy(L1,L2,sizeof(L1));
    }
    fout << L2[G];
}