#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int N=1e6+10,mod=1e9+7;
struct node{
	int wt;
	int id;
	int z;
}d[N];//id表示原位z是哈希值 
bool cmp(node a,node b){
	return a.wt<b.wt;
}
struct nod{
	int wt;
	int id;
	int z;
	bool operator < (const nod&a) const
	{
		return wt>a.wt;
	}
};
int n,m;
int u[N],v[N],t;
bool pd[mod];//哈希判断 
int idx[N],idy[N];//i选到第idx[i]个数 
int wt[N]; 
int ans=0,cnt;
signed main(){
	priority_queue<nod>q;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{cin>>wt[i];
	d[i].id=i;
	d[i].wt=wt[i];
	d[i].z=(rand())%mod;
	pd[(d[i].z*d[i].z)%mod]=1;
	}
	idx[n]=1;
	sort(d+1,d+n+1,cmp);
	for(int i=1;i<=n;i++){
		if(i==n)
		continue;
		if(d[i].wt>0)
	{
			ans+=(d[i].wt*d[1].wt),u[++t]=d[i].id,v[t]=d[1].id,idx[i]=2,pd[(d[1].z*d[i].z)%mod]=1;}
		else
	{
			ans+=(d[i].wt*d[n].wt),u[++t]=d[i].id,v[t]=d[n].id,idy[i]=n-1,pd[(d[n].z*d[i].z)%mod]=1;}
	}
	cnt=m-n+1;
	for(int i=1;i<=n;i++){
		nod now;
		int x=idx[i],y=idy[i];
		if(x==0){
			now.z=(d[i].z*d[y].z)%mod;
			now.wt=(d[i].wt*d[y].wt);
			now.id=i;
		}
		else{
			now.z=(d[i].z*d[x].z)%mod;
			now.wt=(d[i].wt*d[x].wt);
			now.id=i;
		}
		q.push(now);
	}
	while(cnt&&!q.empty()){
		nod now=q.top();
		q.pop();
		nod x;
		int i=now.id;
		if(idx[i]>n||(idy[i]<=0&&idx[i]==0))
		continue;
		if(idx[now.id]==0){idy[i]--;
			x.z=(d[i].z*d[idy[i]].z)%mod;
			x.wt=(d[i].wt*d[idy[i]].wt);
			x.id=i;
			
		}
		else{	idx[i]++;
			x.z=(d[i].z*d[idx[i]].z)%mod;
			x.wt=(d[i].wt*d[idx[i]].wt);
			x.id=i;
		
		}
		q.push(x);
		if(pd[now.z])
		continue; 
		pd[now.z]=1;
		
		ans+=now.wt;
		u[++t]=d[i].id;
		if(idx[i]==0)
		v[t]=d[idy[i]+1].id;
		else
		v[t]=d[idx[i]-1].id;
		cnt--; 
	}
	cout<<ans<<endl;
	for(int i=1;i<=m;i++)
	cout<<u[i]<<" "<<v[i]<<endl;
}