#include <iostream>
#define N 21

using namespace std;

int n, k;
int a[N];
int dp[N][N][N];

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int l = 0; l < n; l++) {
        for (int i = 1; i + l <= n; i++) {
            int j = i + l;
            cout << i << " " << j << endl;
            if (i == j) {
                dp[i][j][0] = a[i];
                cout << dp[i][j][0] << " ";
            } else {
                dp[i][j][0] = dp[i][j - 1][0] + a[j];
                cout << dp[i][j][0] << " ";
                for (int t = 1; t <= l; t++) {
                    for (int k = i; k < j; k++) {
                        for (int f = 0; f < t; f++) {
                            dp[i][j][t] = max(
                                dp[i][j][t],
                                max(dp[i][k][f] +
                                        dp[k + 1][j][t - f],
                                    dp[i][k][f] *
                                        dp[k + 1][j]
                                          [t - f - 1]));
                        }
                        dp[i][j][t] = max(
                            dp[i][j][t],
                            dp[i][k][t] + dp[k + 1][j][0]);
                    }
                    cout << dp[i][j][t] << " ";
                }
            }
            cout << endl;
        }
    }
    cout << dp[1][n][k];
    return 0;
}