#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;
int d[2][10001];
pair <int ,int> v[5001];
int main()
{
    FILE *fin=fopen ("rucsac.in","r");
    FILE *fout=fopen ("rucsac.out","w");
    int n,g,t,i,j,x,px;
    fscanf (fin,"%d%d",&n,&g);
    for (i=1;i<=n;i++){
        fscanf (fin,"%d%d",&x,&px);
        v[i].first=x;
        v[i].second=px;
    }
    //d[0][v[1].first]=v[1].second;
    t=1;
    for (i=1;i<=n;i++){
        for (j=0;j<=g;j++){
            d[t][j]=d[1-t][j];
            if (j>=v[i].first && d[t][j]<d[1-t][j-v[i].first]+v[i].second)
                d[t][j]=d[1-t][j-v[i].first]+v[i].second;
        }
        t=1-t;
    }
    fprintf (fout,"%d",d[1-t][g]);
    return 0;
}