#include<fstream>
using namespace std;
ifstream F("rucsac.in");
ofstream G("rucsac.out");
#define Z 2048
int a[10001],i,n,j,k,l,p=Z,g;
char s[Z];
inline char A()
{
    if(p==Z)
        F.read(s,Z),p=0;
    return s[p++];
}
int B()
{
    int n=0;
    char c;
    for(c=A();isdigit(c);n=n*10+c-48,c=A());
    return n;
}
int main()
{
    for(n=B(),g=B();n--;)
        for(i=B(),j=B(),k+=i,l=min(g,k);l>=i;a[l]=max(a[l],j+a[l-i]),--l);
    return G<<a[g],0;
}