#include <stdio.h>
using namespace std;
int main() {
	const int k = 10, W = 21;
	const int p[] = {0, 21, 64, 45, 73, 87, 86, 91, 64, 44, 85};
	const int w[] = {0, 8, 1, 84, 5, 10, 6, 9, 3, 8};
 
	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;


 
}