#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e6+10;
struct Val{int v,x;}a[N];
struct Node{int fr,to,nxt;ll v;};bool operator<(Node x,Node y){return x.v>y.v;}
int n,m,cnt;ll ans,l,r;pair<int,int>e[N];map<pair<int,int>,bool>vis;priority_queue<Node>q;
void add(int u,int v){ans+=1ll*a[u].v*a[v].v,e[++cnt]={a[u].x,a[v].x},vis[{a[u].x,a[v].x}]=vis[{a[u].x,a[v].x}]=1;}
int main(){
	ios::sync_with_stdio(cin.tie(cout.tie()));
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i].v,a[i].x=i;
	sort(a+1,a+n+1,[](Val a,Val b){return a.v<b.v;});
	if(a[1].v>0)for(int i=2;i<=n;i++)add(1,i);
	else if(a[n].v<0)for(int i=1;i<n;i++)add(i,n);
	else{
		for(int i=2;i<n;i++){
			if(a[i].v<0)add(i,n);
			else add(1,i);
		}add(1,n);
	}for(int i=1;i<=n;i++){
  		if(a[i].v>0&&i!=n)q.push({i,i+1,1,1ll*a[i].v*a[i+1].v});
		else{
			if(i==n)q.push({n,n-1,-1,1ll*a[n].v*a[n-1].v});
			else q.push({i,n,-1,1ll*a[i].v*a[n].v});
		}
	}while(cnt<m){
		Node t=q.top();q.pop();
		if(!vis[{t.fr,t.to}])ans+=t.v,vis[{t.fr,t.to}]=vis[{t.to,t.fr}]=1,e[++cnt]={a[t.fr].x,a[t.to].x};
		if(t.nxt==1){
            if(t.to==n)continue;
			if(t.to+1==t.fr)++t.to;
		}else{
			if(t.to==1)continue;
			if(t.to-1==t.fr)--t.to;
		}if(t.nxt==1&&t.to==n||t.nxt==-1&&t.to==1)continue;
		q.push({t.fr,t.to+t.nxt,t.nxt,1ll*a[t.fr].v*a[t.to+t.nxt].v});
	}cout<<ans<<'\n';
	for(int i=1;i<=cnt;i++)cout<<e[i].first<<' '<<e[i].second<<'\n';
	return 0;
}