#include <bits/stdc++.h>
using namespace std;

int w[10000], p[10000], d[10000], g, n;

int main(){
	cout<<"Cate obiecte ? \n";
	cin>>n;
	cout<<"Care este suma greutatilor ?";
	cin>>g;
	cout<<"Citeste greutatea si valoarea obiectelor \n";
	for(int i=1; i<=n; i++){
		cout<<"Greutatea "<<i<<" = ";
		cin>>w[i];
		cout<<"Valoarea "<<i<<" = ";
		cin>>p[i];
	}
	for(int i=0; i<=n; i++){
		for(int j=g; j>=w[i]; j--){
			d[j]=max(d[j], d[j-w[i]]+p[i]);
		}
	}
	cout<<"Suma maxima este "<<d[g];
	return 0;
}