#include <iostream>
#include<fstream>
using namespace std;
int profit[20001];
int minim(int a,int b)
{
    if(a<b) return a;       //functie care returneaza minimul dintre 2 numere
    else return b;
}
int main()
{int n,G,greutate[5001],valoare[5001],i,j,sum=0;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
f>>n>>G;        //n reprezinta numarul de obiecte,iar G greutatea maxima admisa
for(i=1;i<=n;i++)
    f>>greutate[i]>>valoare[i];       //citesc datele->greutatea si valoarea fiecarui obiect
for(i=1;i<=n;i++)  //pentru fiecare obiect,verific daca pot forma o noua suma optima
     {for(j=sum;j>=1;j--)
        if(profit[j]+valoare[i]>profit[j+greutate[i]]) profit[j+greutate[i]]=profit[j]+valoare[i];
     if(profit[greutate[i]]<valoare[i]) profit[greutate[i]]=valoare[i];
     sum=sum+greutate[i];
     }
for(i=G;i>=1;i--)
if(profit[i]!=0) {g<<profit[i];break;}      //caut greutatea maxima care poate fi atinsa folosind obiectele date
if(i==0) g<<0;  //daca nu se poate obtine aceasta greutate,afisez 0
f.close();
g.close();
    return 0;
}