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

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[2][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,k1,k2;
     for(i=1;i<=N;i++)
        for(j=0;j<=G;j++){
            k1=i%2,k2=(i+1)%2;
            D[k2][j]=D[k1][j];
            if(W[i]<=j)
                D[k2][j]=max(D[k2][j],D[k1][j-W[i]]+P[i]);
        }
    printf("%d\n",D[(N+1)%2][G]);
}