#include <bits/stdc++.h>
using namespace std;

void printknapSack(int W, int wt[], int val[], int n)
{
    int i, w;
    int K[n + 1][W + 1];

    for (i = 0; i <= n; i++)
    {
        for (w = 0; w <= W; w++)
        {
            if (i == 0 || w == 0)
            {
                K[i][w] = 0;
            }
            else if (wt[i - 1] <= w)
            {
                K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]);
            }
             else
            {
                K[i][w] = K[i - 1][w];
            }
        }
    }

    int res = K[n][W];
    cout <<endl<< "Max-Profit: " << res << endl;
    cout <<endl<< "The Items are: "<<endl<<endl;

    w = W;
    for (i = n; i > 0 && res > 0; i--)
    {
        if (res == K[i - 1][w])
            continue;
        else
        {
            cout <<"Item Number: " <<i << " and Weight: "<<wt[i - 1] <<endl;
            res = res - val[i - 1];
            w = w - wt[i - 1];
        }
    }
}

int main()
{
    int nbag,wt,w;
    cout<<"Enter the number of bags: ";
    cin >> nbag;
    int values[nbag];
    cout<<"Enter the values: ";
    for(int i=0; i<nbag; i++){
        cin>> values[i];
    }

    int weight[nbag];
    cout<<"Enter the weights of bags: ";
    for(int i=0; i<nbag; i++){
        cin>> weight[i];
    }    
    cout<<"Enter the maximum weight of the bag: ";
    cin>>w;

    int n = sizeof(values) / sizeof(values[0]);

    printknapSack(w, weight, values, n);

    return 0;
}