#include <bits/stdc++.h>

using namespace std;

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

int main(){
	cout<<"Cite pietre sint? \n";
	cin>>n;
	
	cout<<"care este greutatea maxima?\n";
	cin>>g;
	
	cout<<"\ncare este masa si valoarea fiecarei pietre? \n";
	for(int i=1; i<=n; i++){
		cout<<"\npentru piatra "<<i;
		cout<<"\nmasa = ";
		cin>>m[i];
		cout<<"Valoarea = ";
		cin>>p[i];
	}; 
	
	for(int i=0; i<=n; i++){
		for(int j=g; j>=m[i]; j--){
			d[j]=max(d[j], d[j-m[i]]+p[i]);
		};
	};
	
	cout<<"suma maxima este "<<d[g];
	
	return 0;
}