#include <bits/stdc++.h>

using namespace std;

int n,g;

struct ob{
    int pret;
    int greutate;
}v[10005];

long long d[10005];
long long sol;

int main()
{
	cout<<"n="; cin>>n;
	cout<<"g="; cin>>g;
    for (int i=1;i<=n;++i) {
    	cout<<"greutate["<<i<<"]="; cin>>v[i].greutate;
        cout<<"pret["<<i<<"]="; cin>>v[i].pret;
    }
    d[0]=0;
    for(int i=1;i<=n;++i){
        for(int j=g-v[i].greutate;j>=0;--j){
            if (d[j+v[i].greutate]<d[j]+v[i].pret) {
                    d[j+v[i].greutate]=d[j]+v[i].pret;
                    if(d[j+v[i].greutate] > sol)
                    sol = d[j+v[i].greutate];
            }
        }
    }
    cout<<sol;
}