#include <iostream>
#include<fstream>
#include<string.h>
#define maxn 5001
#define maxg 10001

using namespace std;

int W[maxn], P[maxn];
int Optim[maxg];

int main()
{
    ifstream f("rucsac.in");
    ofstream c("rucsac.out");
    int N,G;
    f>>N>>G;
    for(int i=1;i<=N;i++)
    {
        cout<<"W["<<i<<"]= ";cin>>W[i];
        cout<<endl;
        cout<<"P["<<i<<"]= ";cin>>P[i];
        cout<<endl;
    }
    Optim[0] = 0;
    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] + P[i] )
            {
                Optim[j+W[i]] = Optim[j] + P[i];
                if( Optim[j+W[i]] > sol)
                    sol = Optim[j+W[i]];
            }
        }
        c<<sol;
    f.close();
    c.close();

}