#include<bits/stdc++.h>
using namespace  std;
 
int knap(int *wt, int *p, int c, int n ){
	int d[n+1][c+1];
	for(int i=0;i<=n;i++){
		for(int j=0;j<=c;j++){
			if(i==0 || j==0){
				d[i][j] =0;
			}
			else{
				int inc=0,exe=0;
				if(wt[i-1]<=j){
					inc = p[i-1]+d[i-1][j-wt[i-1]];
				}
				exe = d[i-1][j];
				d[i][j] = max(inc,exe);
			}
		}
	}
	return d[n][c];
}
int main(){
	int wt[] = {1,2,3,5};
	int p[] ={40,20,30,100};
	int c=7;
	int n=4;
	cout<<knap(wt,p,c,n);
}

I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlICBzdGQ7CgppbnQga25hcChpbnQgKnd0LCBpbnQgKnAsIGludCBjLCBpbnQgbiApewoJaW50IGRbbisxXVtjKzFdOwoJZm9yKGludCBpPTA7aTw9bjtpKyspewoJCWZvcihpbnQgaj0wO2o8PWM7aisrKXsKCQkJaWYoaT09MCB8fCBqPT0wKXsKCQkJCWRbaV1bal0gPTA7CgkJCX0KCQkJZWxzZXsKCQkJCWludCBpbmM9MCxleGU9MDsKCQkJCWlmKHd0W2ktMV08PWopewoJCQkJCWluYyA9IHBbaS0xXStkW2ktMV1bai13dFtpLTFdXTsKCQkJCX0KCQkJCWV4ZSA9IGRbaS0xXVtqXTsKCQkJCWRbaV1bal0gPSBtYXgoaW5jLGV4ZSk7CgkJCX0KCQl9Cgl9CglyZXR1cm4gZFtuXVtjXTsKfQppbnQgbWFpbigpewoJaW50IHd0W10gPSB7MSwyLDMsNX07CglpbnQgcFtdID17NDAsMjAsMzAsMTAwfTsKCWludCBjPTc7CglpbnQgbj00OwoJY291dDw8a25hcCh3dCxwLGMsbik7Cn0=