#include<stdio.h>
#include<algorithm>
using namespace std;
typedef struct val
{
    int v,g;
}val;

val v[5001];
int s[2][10001];

int main()
{
    freopen("rucsac.in","r",stdin);
    freopen("rucsac.out","w",stdout);
    int n,g,i,j,lin=1,sol=0;
    scanf("%d%d",&n,&g);
    for(i=1;i<=n;i++)
        scanf("%d%d",&v[i].g,&v[i].v);
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=g;j++)
        {
            if(j-v[i].g<0)
                s[lin][j]=s[1-lin][j];
            else
                s[lin][j]=max(s[1-lin][j],s[1-lin][j-v[i].g]+v[i].v);
        }
        lin=1-lin;
    }
    for(j=0;j<=g;j++)
        if(s[1-lin][j]>sol)
            sol=s[1-lin][j];
    printf("%d\n",sol);
    return 0;
}