#include <bits/stdc++.h>
using namespace std;
 
int knapsack(int cap,vector<int> wt, vector<int> pro,int n) {
	if(n==0 || cap==0) return 0;
	if(wt[n-1] > cap) return knapsack(cap,wt,pro,n-1);
	return max(knapsack(cap,wt,pro,n-1),
			   pro[n-1] + knapsack(cap-wt[n-1],wt,pro,n-1)
			 );
 
}
int main() {
	vector<int> weight = {3,2,4};
	vector<int> profit = {6,8,7};
	int capacity = 8;
	cout<<knapsack(capacity,weight,profit,profit.size());
	return 0;
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgppbnQga25hcHNhY2soaW50IGNhcCx2ZWN0b3I8aW50PiB3dCwgdmVjdG9yPGludD4gcHJvLGludCBuKSB7CglpZihuPT0wIHx8IGNhcD09MCkgcmV0dXJuIDA7CglpZih3dFtuLTFdID4gY2FwKSByZXR1cm4ga25hcHNhY2soY2FwLHd0LHBybyxuLTEpOwoJcmV0dXJuIG1heChrbmFwc2FjayhjYXAsd3QscHJvLG4tMSksCgkJCSAgIHByb1tuLTFdICsga25hcHNhY2soY2FwLXd0W24tMV0sd3QscHJvLG4tMSkKCQkJICk7CgkKfQppbnQgbWFpbigpIHsKCXZlY3RvcjxpbnQ+IHdlaWdodCA9IHszLDIsNH07Cgl2ZWN0b3I8aW50PiBwcm9maXQgPSB7Niw4LDd9OwoJaW50IGNhcGFjaXR5ID0gODsKCWNvdXQ8PGtuYXBzYWNrKGNhcGFjaXR5LHdlaWdodCxwcm9maXQscHJvZml0LnNpemUoKSk7CglyZXR1cm4gMDsKfQ==