#include <cstdio>
#include <algorithm>
using namespace std;


int a[5002][1000];
int n,g;




void citire()
{
    scanf("%d %d",&n,&g);
}

void calc()
{
    int w,p;
    for(int i=1;i<n;i++)
    {
        scanf("%d %d\n",&w,&p);
        for(int j=0;j<=g;j++)
            a[i][j]=max(a[i-1][j],p+a[i-1][j-w]);
    }
    printf("%d",a[n-1][g-1]);
}




int main()
{

    freopen("rucsac.in","r",stdin);
    citire();
    calc();

    return 0;
}