#include <iostream>
#include <cstring>
#include <fstream>
#define max_n 5001
#define max_g 10001
using namespace std;
int n,g;
int a[3][max_g],gr[max_n],c[max_n];

int main()
{
    int i,j;
    freopen("rucsac.in","r",stdin);
    freopen("rucsac.out","w",stdout);
    scanf("%d%d",&n,&g);
    for(i=1; i<=n; i++)
    {
        scanf("%d%d", &gr[i], &c[i]);
    }

    for(i=1; i<=n; i++)
    {
        for(j=1; j<=g; j++)
        if(gr[i]<=j) a[2][j]=max(a[1][j],a[1][j-gr[i]]+c[i]);
        else a[2][j]=a[1][j];
        memcpy(a[1],a[2],sizeof(a[2]));
    }

    printf("%d\n",a[2][g]);

    return 0;

}