#include <fstream>
#include <algorithm>
using namespace std;

ifstream cin ("rucsac.in");
ofstream cout ("rucsac.out");

int n, g, W[5001], V[5001], Optim[10001];

int main(){
    cin >> n>>g;
    for (int i = 1; i <=n;++i)
    cin >> W[i] >> V[i];

    int sol = 0;
    for (int i = 1;i <=n;++i)
        for (int j = g-W[i]; j >=0;--j)
        {
            if (Optim[j+W[i]]< Optim[j] + V[i])
                Optim[j+W[i]] = Optim[j] + V[i];
				if( Optim[j+W[i]] > sol)
					sol = Optim[j+W[i]];
        }
    cout << sol;
}