#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <bitset>

using namespace std;
typedef long long ll;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll n, k;
    cin >> n >> k;
    vector<vector<pair<ll, int>>> dp(n, vector<pair<ll, int>>(k, {0, 0}));
    vector<ll> a(n);
    for(int i = 0; i < n; ++i){
        cin >> a[i];
    }
    dp[0][0].first = a[0];
    for(int i = 1; i < n; ++i){
        dp[i][0].first = min(dp[i - 1][0].first, a[i]);
        dp[i][0].second = -1;
    }
    for(int i = 1; i < k; ++i){
        for(int j = 1; j < k; ++j){
            ll c = a[i];
            for(int v = 0; v < i; ++v){
                c = min(c, a[i - v]);
                if(dp[i - v - 1][j - 1].first + c >= dp[i][j].first){
                    dp[i][j].first = max(dp[i - v - 1][j - 1].first + c, dp[i][j].first);
                    dp[i][j].second = i - v - 1;
                }
            }
        }
    }
    for(int i = k; i < n; ++i){
        for(int j = 1; j < k; ++j){
            ll c = a[i];
            for(int v = 0; v < i; ++v){
                c = min(c, a[i - v]);
                if(dp[i - v - 1][j - 1].first + c >= dp[i][j].first){
                    dp[i][j].first = max(dp[i - v - 1][j - 1].first + c, dp[i][j].first);
                    dp[i][j].second = i - v - 1;
                }
            }
        }
    }
    cout << dp[n - 1][k - 1].first << "\n";
    int i = n - 1;
    int j = k - 1;
    vector<int> res;
    for(int x = 0; x < k - 1; ++x){
        res.push_back(dp[i][j - x].second + 1);
        i = dp[i][j - x].second;
    }
    for(int i = res.size() - 1; i > -1; --i){
        cout << res[i] << " ";
    }
    cout << endl;
}