#include <fstream>
using namespace std;
int v[50001];
int main()
{
   int i,j,x,y,n,g;
    ifstream f("rucsac.in");
    ofstream h("rucsac.out");
    f>>n>>g;
    for(i=1;i<=n;i++)
    {
        f>>x>>y;
        for(j=g;j>=x;j--)
            if(v[j]<v[j-x]+y)
            v[j]=v[j-x]+y;
    }
    h<<v[g];
    return 0;
}
/*3 5
2 3
3 2
3 4

pentru ce e  for(j=G-x;j>=0;j--) la problema rucsacului?
.: adica dc e j=g-x
Miron Dorin: poi..
Miron Dorin: ai un vector
Miron Dorin: pozitia din vector inseamna greutatea
Miron Dorin: si valoarea din el inseamna valoarea maxima
.: aa
.: un fel de vector caracteristic nu?
Miron Dorin: un fel...
Miron Dorin: unde tu calculezi in v[1]
Miron Dorin: valoarea maxima care o poti forma cadn ai la dispozitie
Miron Dorin: doar un kg
Miron Dorin: v[2] =val maxima cu 2 kg
Miron Dorin: v[g]= val maxima cu g kg
Miron Dorin: si g-x... inseamna greutatea maxima -
Miron Dorin: greutatea pe care deja ai pus-o*/