#include <cstdio>
#define MAXG 10005
#define MAXN 5005

using namespace std;
/**
Se da o multime formata din N obiecte, fiecare fiind caracterizat de o greutate si un profit. Sa se gaseasca o submultime
de obiecte astfel incat suma profiturilor lor sa fie maxima, iar suma greutatilor lor sa nu depaseasca o valoare G.
Date de intrare

Pe prima linie a fişierul rucsac.in se vor gasi valorile N si G,
cu semnificatia din enunt. Pe urmatoarele N linii se vor gasi perechile de valori Wi si Pi,
reprezentand greutatea, respectiv profitul obiectului i.
Date de ieşire

În fişierul de ieşire rucsac.out se va afisa o singura valoare Pmax,
profitul maxim care poate fi obtinut respectand conditia problemei.
Restricţii

    1 ≤ N ≤ 5000
    1 ≤ G ≤ 10000
    0 ≤ Wi, Pi ≤ 10000

*/
int N,G,W[MAXN],P[MAXN],D[MAXN][MAXG];

void read();
void DProgramming();

int main(){
    freopen("rucsac.in","r",stdin);
    freopen("rucsac.out","w",stdout);
    read();
    DProgramming();
    return 0;
}
void read(){
    scanf("%d %d ",&N,&G);
    for(int i=1;i<=N;i++)scanf("%d %d ",&W[i],&P[i]);
}
void DProgramming(){
     int i,j;
     for(i=1;i<=N;i++)
        for(j=0;j<=G;j++){
            D[i][j]=D[i-1][j];
            if(W[i]<=j)D[i][j]=(D[i][j]>D[i-1][j-W[i]]+P[i]?D[i][j]:D[i-1][j-W[i]]+P[i]);
        }
    printf("%d\n",D[N][G]);
}