import java.util.*;
public class knapsack{
    static int[][] dp;
    static int knap(int[] wt, int[] v, int n, int W){
        if(n==0 || W==0){
            return 0;
        }
        if(dp[n][W]!=-1){
            return dp[n][W];
        }
        if(wt[n-1]>W){
            dp[n][W]= knap(wt,v,n-1,W);
        }
        else{
            int include = v[n-1]+knap(wt,v,n-1,W-wt[n-1]);
            int exclude = knap(wt,v,n-1,W);
            dp[n][W] = Math.max(include, exclude);
        }
        return dp[n][W];

    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        System.out.println("\nENter number of items: ");
        int n = sc.nextInt();
        int w[] = new int[n];
        int values[] = new int[n];

        System.out.println("\nEnter weights: ");
        for(int i =0;i<n;i++){
            w[i] = sc.nextInt();
        }
        System.out.println("\nEnter values: ");
        for(int i =0;i<n;i++){
            values[i] = sc.nextInt();
        }

        System.out.println("\nEnter capacity: ");
        int W = sc.nextInt();

        dp = new int[n+1][W+1];
        for(int i =0;i<=n;i++){
            for(int j=0;j<=W;j++){
                dp[i][j] = -1;
            }
        }
        int ans = knap(w,values,n,W);
        System.out.println("\nMax value: "+ans);
        sc.close();
    }

}