评测记录

#include <bits/stdc++.h>
#define pii pair<long long,long long>
#define ll long long
using namespace std;

const int MAXN=1e6+5;

struct data{
	ll val,id;
	ll operator+(const data x) const {
		return val+x.val;
	}ll operator*(const data x) const {
		return val*x.val;
	}
}nd[MAXN]; 

ll cur[MAXN];

ll n,m;

ll ans=0;

set<pii > st;

void init(){
	sort(nd+1,nd+1+n,[](data x,data y){
		return x.val<y.val;
	});
}//排序 

struct node{
	ll u,v,w;
	bool operator<(const node x) const{
		return w>x.w;
	}
};//

pii mkpr(ll x,ll y){
	return make_pair(min(x,y),max(x,y));
}//新建一条边的pair 

ll SMT(){
	ll res=0;
	for(ll i=1;i<n;++i){
		res+=min(nd[i]*nd[1],nd[i]*nd[n]);
		
		if(nd[i]*nd[1]<nd[i]*nd[n])
			st.insert(mkpr(nd[i].id,nd[1].id));
		else
			st.insert(mkpr(nd[i].id,nd[n].id));
	}
	return res;
}//最小生成树 

priority_queue<node> q;

void move(ll u){
	if(nd[u].val>0) cur[u]++;
	else cur[u]--;
	if(cur[u]>n || cur[u]<1) return ;
	q.push(node{u,cur[u],nd[u]*nd[cur[u]]});
}//把节点u的下一个选择加到堆里 

void solve(ll& res,ll rem){
	for(ll i=1;i<=n;++i){
		if(nd[i].val>0){
			q.push(node{i,1,nd[i]*nd[1]});
			cur[i]=1;
		}else{
			q.push(node{i,n,nd[i]*nd[n]});
			cur[i]=n;
		}
	}
	
	node d;
	
	while(rem){
		d=q.top();q.pop();
		move(d.u);
		if(d.u==d.v || st.count(mkpr(nd[d.v].id,nd[d.u].id))) continue;
		
		st.insert(mkpr(nd[d.v].id,nd[d.u].id));
		
		rem--;
		res+=d.w;
	}
}//加入非树边 

void read(){
	cin>>n>>m;
	for(ll i=1;i<=n;++i){
		cin>>nd[i].val;
		nd[i].id=i;
	}
}//

void print(){
	for(auto e:st)
		printf("%lld %lld\n",e.first,e.second);
}//

int main(){
	read();
	
	if(n<=1){
		printf("0");
		return 0;
	}
	
	init();
	
	ll ans=SMT();
	solve(ans,m-n+1);
	
	printf("%lld\n",ans);
	print();
	return 0;
}