#include <iostream>
#include <vector>

#define inf 100000000

using namespace std;

vector<int> villages(300);
int pref[300];
int f[31][301];
int pa[31][301];
int m[301][301];

int cost(int l, int r){
    l--; r--;
    int ml = m[l][r];
    return villages[ml]*((ml - l + 1) - (r - ml + 1))- (pref[ml+1] - pref[l]) + (pref[r+1] - pref[ml]);
}

int main() {
    int v, p;
    cin >> v >> p;

    for (int i = 0; i < v; i++) {
        cin >> villages[i];
    }

    pref[0] = 0;
    for (int i = 1; i <= v; i++) {
        pref[i] = pref[i - 1] + villages[i-1];
    }

    int i;
    for(int left = 0; left < v; left++){
        for(int r = left; r <= v; r++){
            int mid = (r - left ) / 2 + left;
            m[left][r] = mid;
        }
    }

    for(i = 0; i <= v + 1; i++){
        pa[i][0] = inf;
    }

    for(i = 1; i <= v; i++){
        f[1][i] = cost(1, i);
    }

    for (int k = 2; k <= p; k++) { // порядок перебора состояний следует из неравенств
        for (int n = v; n >= k; n--) { // порядок перебора состояний следует из неравенств
            f[k][n] = inf;
            for (i = 1/*pa[k - 1][n]*/; i <= /*pa[k][n + 1]*/ v; i++) { // уже посчитаны
                int tmp = f[k - 1][i]  + cost(i+1, n);
                if (tmp < f[k][n]) {
                    f[k][n] = tmp;
                    pa[k][n] = i;
                }
            }
        }
    }

    cout << f[p][v] << endl;

    vector<int> posts;
    int tmp = v-1;
    for(int k = p; k > 0; k--){
        posts.push_back(m[pa[k][tmp]+1][tmp]);
 //       cout << "k = " <<  k << " m = " << m[pa[k][tmp]+1][tmp] << " p = " << pa[k][tmp] << " tmp = " << tmp << endl;
        tmp = pa[k][tmp];
    }

    for(int k = posts.size()-1; k >= 0; k--){
        cout << villages[posts[k]] << " " ;
    } cout << endl;

    return 0;
}