#include <bits/stdc++.h> 

int helperdp(vector<int> weight,vector<int>value,int n,int maxw,int index,int temp,int w,vector<vector<int>>& dp)
{
	if(index==n)
		return temp;

	if(dp[index][w]!=-1)
		return dp[index][w];

	int y = helperdp(weight,value,n,maxw,index+1,temp,w,dp);
	int x = 0;
	if(w+weight[index]<=maxw)
		x = helperdp(weight,value,n,maxw,index+1,temp+value[index],w+weight[index],dp);

	return dp[index][w] = max(x,y);
	
}

int knapsack(vector<int> weight, vector<int> value, int n, int maxWeight) 
{
	vector<vector<int>> dp(n,vector<int>(maxWeight+1,-1));
	return helperdp(weight,value,n,maxWeight,0,0,0,dp);
}