#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
    vector<int> A,B;

struct ruck
{
    int w,p;
} v[5001]   ;

int main()
{
    int n,G;
    ifstream f("rucsac.in");
    ofstream g("rucsac.out");
    f>>n>>G;
    A.resize(G);
    B.resize(G);
    for(int i=1;i<=n;i++)
        f>>v[i].w>>v[i].p;
    for(int i=0;i<v[1].w;i++)
        A[i]=0;
    for(int i=v[1].w;i<=G;i++)
        A[i]=v[1].p;
    for(int i=2;i<=n;i++)
    {
        B[0]=0;
        for(int j=0;j<=G;j++)
        {
            if(v[i].w>j)
                B[j]=A[j];
            else B[j]=max(A[j],A[j-v[i].w]+v[i].p);
        }
        A.swap(B);
    }
    g<<A[G];
    return 0;
}