#include <fstream>
#include <iostream>

using namespace std;

long long int n,g,w[5001],p[5001],cost[5001][10001],maxim;

int main()
{
    ifstream in("rucsac.in");
    ofstream out("rucsac.out");
    int i,j;
    in>>n>>g;
    for(i=1; i<=n; i++)
    {
        in>>w[i]>>p[i];
    }
    for(i=1; i<=n; i++)
        for(j=g; j>-1; j--)
            if(cost[i-1][j]<cost[i-1][j-w[i]]+p[i] && j-w[i]>-1)
                cost[i][j]=cost[i-1][j-w[i]]+p[i];
            else cost[i][j]=cost[i-1][j];
    cout<<cost[n][g];
    in.close();
    out.close();
    return 0;
}