8

#include <stdio.h>
using namespace std;
int main() {
    const int k = 10, W = 22;
    const int p[] = {0, 71, 28, 43, 89, 17, 59, 33, 98, 64, 92};
    const int w[] = {0, 2, 7, 3, 10, 3, 7, 6, 4, 9, 10};

    int A[k + 1][W + 1];
    for (int i = 0; i <= k; i++) A[i][0] = 0;
    for (int n = 0; n <= W; n++) A[0][n] = 0;
    for (int s = 1; s <= k; s++) {
        for(int n = 1;n<=W;n++) {
            A[s][n] = A[s-1][n];
            if (n >= w[s] && (A[s - 1][n - w[s]] + p[s] > A[s][n])) A[s][n] = A[s - 1][n - w[s]] + p[s];
        }

    }
    for (int i = 0; i <= k; i++) {
        for (int j = 0; j <= W; j++)
            printf("%d ", A[i][j]);
        printf("\n");
    }
    printf("\n%d\n", A[k][W]);
    int arr[k];
    int brd = 0;
    int a = k, b = W, t = A[a][b];
    while (a && b) {
        a --;
        if (t != A[a][b]) {
            b -= w[a + 1];
            t = A[a][b];
            arr[brd++] = a + 1;
        }
    }

    for (int i = brd - 1; i >= 0; i --) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;



}