#include <stdio.h>
#include <iostream>
using namespace std;
FILE *f,*g;
int n,gr,a[3][1002],lp,lc;
struct
{
    int c,g;
}v[5002];
void read()
{
    fscanf(f,"%d %d",&n,&gr);
    for(int i=1;i<=n;i++)
        fscanf(f,"%d %d",&v[i].g,&v[i].c);
}
void dinamica()
{
    int i,j;
    lp=0;
    lc=1;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=gr;j++)
            if(v[i].g<=j)
                a[lc][j]=max(a[lp][j-v[i].g]+v[i].c,a[lp][j]);
            else
                a[lc][j]=a[lp][j];
        lp=1-lp;
        lc=1-lc;
    }
    fprintf(g,"%d",a[lp][gr]);
}
int main()
{
    f=fopen("rucsac.in","r");
    g=fopen("rucsac.out","w");
    read();
    dinamica();
    return 0;
}