#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define endl '\n'
#define sz(x) (int)(x.size())
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define uniq(v) (v).erase(unique(all(v)),(v).end())
typedef tree<int, null_type,less<int>,rb_tree_tag, tree_order_statistics_node_update> pbds;//A.find_by_order(x), A.order_of_key(x)
const long long INF=1e18;
const int mod=1e9+7; // 998244353;
void dgb_out () { cerr << endl; }
template < typename Head, typename... Tail >
void dgb_out ( Head H, Tail... T) { cerr <<' ' << H; dgb_out (T...); }
#ifndef ONLINE_JUDGE
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dgb_out(__VA_ARGS__)
#else
#define dbg(...)
#endif
int m, n;
vector<long long> dp_before, dp_cur;
vector<int> arr, pref, ans;
const int N = 1e5 + 5, K = 205;
int par[K][N];
// int cur_l = 1, cur_r = 0, ans = 0;
long long C(int i, int j){
return -(pref[j] - (i == 0 ? 0 : pref[i-1])) * (pref[n-1] - pref[j]);
}
void print_ans(int i, int k){
if(k >= 0){
cout<<i<<" "<<par[k][i]<<endl;
ans.push_back(par[k][i]);
print_ans(par[k][i], k-1);
}
}
// compute dp_cur[l], ... dp_cur[r] (inclusive)
void compute(int l, int r, int optl, int optr, int c_k) {
if (l > r)
return;
int mid = (l + r) >> 1;
pair<long long, int> best = {LLONG_MAX, -1};
for (int k = optl; k <= min(mid, optr); k++) {
best = min(best, {(k ? dp_before[k - 1] : 0) + C(k, mid), k});
}
dp_cur[mid] = best.first;
int opt = best.second;
par[c_k][mid] = opt;
compute(l, mid - 1, optl, opt, c_k);
compute(mid + 1, r, opt, optr, c_k);
}
long long solve() {
dp_before.assign(n,0);
dp_cur.assign(n,0);
for (int i = 0; i < n; i++)
dp_before[i] = C(0, i);
for (int i = 1; i < m; i++) {
compute(0, n - 1, 0, n - 1, i);
dp_before = dp_cur;
}
return dp_before[n - 1];
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
//freopen("input.in","r", stdin);
//freopen("output.out","w", stdout);
//pbds A;
int tc=1;
// cin>>tc;
while(tc--)
{
cin>>n>>m;
arr.resize(n), pref.resize(n);
// freq.resize(n+1, 0);
for(int i=0; i<n; i++){
cin>>arr[i];
pref[i] = (i == 0 ? 0 : pref[i-1]) + arr[i];
}
m++;
cout<<-solve()<<endl;
print_ans(n-1, m-1);
sort(all(ans)); ans.pop_back();
for(auto& point : ans)cout<<point + 1<<" ";
}
return 0;
}
// 7 3
// 4 1 3 4 0 2 3
