#include <iostream>
#include <vector>

using namespace std;

int n, m;
vector <int> input;

int value(vector <int> &values, vector <int> &temp, int left, int right){

    int center = (left + right) / 2;

    int r_to_m;
    int m_to_l;

    if(!((right - left + 1) % 2)){
        r_to_m = temp[right + 1] - temp[center + 1];
        m_to_l = temp[center] - temp[left];
        return r_to_m - m_to_l - values[center];
    } else {
        int r_to_m = temp[right + 1] - temp[center + 1];
        int m_to_l = temp[center] - temp[left];
        return r_to_m - m_to_l;
    }
}


int main() {
    int temp_n;
    int temp_rasst;
    int some = 0;
    int new_one;

    cin >> n >> m;

    vector <int> total(m);
    vector <vector <int>> search(m + 1, vector <int>(n + 1, 0));
    vector <int> sumka(n + 1);

    for(int i = 0; i < sumka.size(); i++){
        sumka[i] = 0;
    }

    for(int i = 0; i < n; i++){
        int x;
        cin >> x;
        input.push_back(x);
    }

    for(int i = 1; i < n + 1; i++){
        sumka[i] = sumka[i - 1] + input[i - 1];
    }


    int maximum = sumka[n] - sumka[0];

    for(int i = 1; i < n + 1; i++){
        search[0][i] = maximum;
    }

    int temp_min;

    for(int i = 1; i < m + 1; i++){
        for (int j = 1; j < n + 1; j++){
            temp_min = maximum;
            for (int z = 0; z < j; z++){
                temp_min = min(temp_min, search[i - 1][z] + value(input, sumka, z, j - 1));
            }
            search[i][j] = temp_min;
        }
    }

    int result = search[m][n];
    cout << result << endl;

    temp_n = n;

    for(int i = m; i > 0; i--){
        for(int j = 0; j <= temp_n; j++){
            if(search[i][temp_n] == search[i - 1][j] + value(input, sumka, j, temp_n - 1)){
                temp_min = new_one;
                temp_rasst = j;
            }
        }

        total[some++] = input[(temp_rasst + temp_n - 1) / 2];
        temp_n = temp_rasst;

    }

    for(int i = m - 1; i >= 0; i--)
        cout << total[i] << " ";

    return 0;
}