#include <fstream>
using namespace std;

ifstream f("rucsac.in");
ofstream g("rucsac.out");

const int maxn = 5001;

int n,k,l;
int w[maxn],p[maxn],d[2][10001];

int Maxim(int a, int b)
{
    if(a>b) return a;
    return b;
}

void Read()
{
    f>>n>>k;
    for(int i=1;i<=n;i++)
        f>>w[i]>>p[i];
}

int main()
{
    Read();

    l=0;
    for(int i=1;i<=n;i++)
    {
        l = 1-l;
        for(int j=1;j<=k;j++)
            if(j-w[i]>=0)
                d[l][j] = Maxim(d[1-l][j], d[1-l][j-w[i]]+p[i]);
            else
                d[l][j] = d[1-l][j];
    }

    g<<d[l][k];

    return 0;
}