#include<stdio.h>
#include <iostream>
using namespace std;
#define W 21
#define N 6
int a[N][W] = {0};
void backpage(){
int w[] = { 0,2,3,4,5,9 };
int v[] = { 0,3,4,5,8,10 };
for (int k = 1; k < N; k++)
for (int C = 1; C < W; C++)
{
if (w[k] > C) a[k][C] = a[k - 1][C];
else {
int value1 = v[k]+a[k-1][C-w[k]];
int value2 = a[k - 1][C];
if (value1 > value2) a[k][C] = value1;
else { a[k][C] = value2; }
}
}
}
int main() {
backpage();
for (int in = 0; in < N; in++)
{
for (int wn = 0; wn < W; wn++)
{
std::cout << a[in][wn] << " ";
}
std::cout << endl;
}
//cout << a[5][20];
return 0;
}
