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

int KnapSack(int val[], int wt[], int n, int W)
{
    int dp[W+1];
    memset(dp, 0, sizeof(dp));

    for(int i=0; i < n; i++)
        for(int j=W; j>=wt[i]; j--)
            dp[j] = max(dp[j] , val[i] + dp[j-wt[i]]);

    return dp[W];
}

int main()
{
    int val[] = {3, 7, 10, 12, 17, 19, 21}, wt[] = {1, 3, 4, 5, 8, 10, 11}, W = 100, n = 7;
    cout << KnapSack(val, wt, n, W) << endl;
    return 0;
}