#include <iostream>
#include <fstream>
#define max_n 5001
#define max_g 10001
using namespace std;
int n,g;
int a[max_n][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[i][j]=max(a[i-1][j],a[i-1][j-gr[i]]+c[i]);
    else a[i][j]=a[i-1][j];

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

    return 0;

}