8

#include <iostream>
#include <limits.h>
#include <algorithm>
#include <vector>

using namespace std;

const int w = 14;
const int n = 10;

const int u[n + 1] = {0, 11, 94, 61, 52, 47, 78, 73, 90, 91, 97};
const int v[n + 1] = {0, 6, 9, 4, 6, 10, 10, 4, 2, 3, 3};

int dp[n + 1][w + 1];

int main(void) {
    for (int i = 0; i <= n; ++ i)
        dp[i][0] = 0;
    for (int i = 0; i <= w; ++ i)
        dp[0][i] = 0;

    for (int i = 1; i <= n; ++ i) {
        for (int j = 1; j <= w; ++ j) {
            dp[i][j] = dp[i - 1][j];
            if (v[i] <= j)
                dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + u[i]);
        }
    }

    for (int i = 0; i <= n; ++ i) {
        for (int j = 0; j <= w; ++ j)
            cout << dp[i][j] << " ";
        cout << endl;
    }
    vector<int> p;
    int i = n;
    int j = w;
    int x = dp[i][j];
    while (i != 0 && j != 0) {
        i --;
        if (x != dp[i][j]) {
            j -= v[i + 1];
            x = dp[i][j];
            p.push_back(i + 1);
        }
    }


    reverse(p.begin(), p.end());
    int a = 0;
    int b = 0;
    cout << endl;
    for (int i = 0; i < p.size(); ++ i) {
        cout << p[i] << " ";
        a += u[p[i]];
        b += v[p[i]];
    }
    cout << endl << a << " " << b << endl;
    return 0;
}