#include <bits/stdc++.h>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
const int NMAX=5001;
int d[2][NMAX];

struct ruc
{
    int w, p;
}v[NMAX];

int main()
{
    int n, G;
    f >> n >> G;
    for(int i=1; i<=n; i++)
    {
        f >> v[i].w >> v[i].p;
    }
    for(int i=1; i<=n; i++)
        for(int j=0; j<=G; j++)
        {
            if(j>=v[i].w)
            {
                d[i%2][j]=max(d[(i-1)%2][j], d[(i-1)%2][j-v[i].w]+v[i].p);
            }else
                d[i%2][j]=d[(i-1)%2][j];

        }


    g << d[n%2][G];
}