#include <iostream>
#include <fstream>

using namespace std;

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

int g[5001],p[5001],d[10001][10001];

int main()
{
    int n,greutate;

    f>>n>>greutate;

    for(int i=1;i<=n;i++)
    {
        f>>g[i]>>p[i];
    }

    for(int i=0;i<=n;i++)
    {
        for(int s=0;s<=greutate;s++)
        {
            d[i][s]=d[i-1][s];
            if(g[i]<=s)
                d[i][s]=max(d[i][s], d[i-1][s-g[i]]+p[i]);
        }
    }

    gg<<d[n][greutate];

    return 0;
}