#include <bits/stdc++.h>

using namespace std;

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

int main(){
	cout<<"Nr de pietre: \n"; cin>>n;
	cout<<"G: \n"; cin>>g;
	cout<<"\n masa si valoarea fiecarei pietre? \n";
	for(int i=1; i<=n; i++){
		cin>>m[i]>>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: "<<d[g];
	
	return 0;
}