强烈谴责卡常出题人/fn

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e6+1;
struct Val{ll v,x;}a[N];inline bool cmp(Val a,Val b){return a.v<b.v;}
struct Node{int fr,to,nxt;ll v;};inline bool operator<(Node x,Node y){return x.v>y.v;}
int n,m,cnt;ll ans;pair<int,int>e[N];unordered_map<ll,bool>vis;priority_queue<Node>q;
inline void add(int u,int v){ans+=a[u].v*a[v].v,e[++cnt]={a[u].x,a[v].x},vis[a[u].x<<20|a[v].x]=vis[a[v].x<<20|a[u].x]=1;}
inline int read(){
    int x;bool f=0;char ch;
    while(!isdigit(ch=getchar()))if(ch=='-')f=1;
    x=ch^'0';
    while(isdigit(ch=getchar()))x=(x<<3)+(x<<1)+(ch^'0');
    return f?-x:x;
}inline void write(ll x){if(x<10)putchar(x^48);else write(x/10),putchar(x%10^48);}
inline void fushu(ll x){if(x<0)putchar('-'),write(-x);else write(x);}
int main(){
	n=read(),m=read();
	for(register int i=1;i<=n;i++)a[i].v=read(),a[i].x=i;
	sort(a+1,a+n+1,cmp);
	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(register int i=2;i<n;i++){
			if(a[i].v<0)add(i,n);
			else add(1,i);
		}add(1,n);
	}for(register int i=1;i<=n;i++){
  		if(a[i].v>=0&&i!=n)q.push({i,i+1,1,a[i].v*a[i+1].v});
		else{
			if(i==n)q.push({n,n-1,-1,a[n].v*a[n-1].v});
			else q.push({i,n,-1,a[i].v*a[n].v});
		}
	}while(cnt<m){
		Node t=q.top();q.pop();
		if(!vis[a[t.fr].x<<20|a[t.to].x])ans+=t.v,vis[a[t.fr].x<<20|a[t.to].x]=vis[a[t.to].x<<20|a[t.fr].x]=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,(ll)a[t.fr].v*a[t.to+t.nxt].v});
	}fushu(ans),putchar('\n');
	for(register int i=1;i<=cnt;i++)write(e[i].first),putchar(' '),write(e[i].second),putchar('\n');
	return 0;
}