最后一个包三个点过不去。

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 1e6+100;
int n,m;
ll a[N];
// priority_queue<int,vector<int>,greater<int> > q,q1;
struct cmp
{
	unsigned long long operator()(const pair<int,int>& x)const
	{
		return ((unsigned long long)x.first<<32ull)^(unsigned long long)(x.second)^((unsigned long long)(x.second)<<31);
	}
};
unordered_set<pair<int,int>,cmp> s;
inline void in(const int& x,const int& y)
{
	// cout<<"A"<<x<<' '<<y<<'\n';
	s.insert({min(x,y),max(x,y)});
}
inline bool g(const int& x,const int& y)
{
	if(x==y)return 1;
	return s.find({min(x,y),max(x,y)})!=s.end();
}
struct node
{
	int x,y;
	inline bool operator<(const node &z)const
	{
		return y<z.y;
	}
}b[N],c[N];
int bcnt[N],ccnt[N];
int cnt1,cnt2;
struct edge
{
	int f,t;
	ll w;
	inline bool operator<(const edge& x)const
	{
		return w>x.w;
	}
};
priority_queue<edge> q;
inline void add(int x)
{
	if(a[x]>0)
	{
		while(bcnt[x]<=cnt1&&g(b[++bcnt[x]].x,x));
		if(bcnt[x]<=cnt1)
		{
			q.push({x,b[bcnt[x]].x,a[x]*b[bcnt[x]].y});
		}
		while(ccnt[x]<=cnt2&&g(c[++ccnt[x]].x,x));
		if(ccnt[x]<=cnt2)
		{
			q.push({x,c[ccnt[x]].x,a[x]*c[ccnt[x]].y});
		}
	}
	else
	{
		while(bcnt[x]>0&&g(b[--bcnt[x]].x,x));
		if(bcnt[x]>0)
		{
			q.push({x,b[bcnt[x]].x,a[x]*b[bcnt[x]].y});
		}
		while(ccnt[x]>0&&g(c[--ccnt[x]].x,x));
		if(ccnt[x]>0)
		{
			q.push({x,c[ccnt[x]].x,a[x]*c[ccnt[x]].y});
		}
	}
}
signed main()
{
	cin>>n>>m;
	int m1=m;
	cnt1=0,cnt2=0;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		// q.push(i);
		if(a[i]>0)b[++cnt1]={i,a[i]};
		else c[++cnt2]={i,a[i]};
	}
	for(int i=1;i<=n;i++)
	{
		if(a[i]<=0)
		{
			bcnt[i]=cnt1+1;
			ccnt[i]=cnt2+1;
		}
	}
	sort(b+1,b+1+cnt1);
	sort(c+1,c+1+cnt2);
	ll ans=0;
	if(cnt1&&cnt2)
	{
		for(int i=1;i<=cnt1;i++)
		{
			m--;
			in(c[1].x,b[i].x);
			// ans+=c[1].y*b[i].y;
		}
		for(int i=2;i<=cnt2;i++)
		{
			m--;
			in(c[i].x,b[cnt1].x);
			// ans+=c[i].y*b[cnt1].y;
			// in(c[i].x,b[cnt1].x);
		}
	}
	else if(cnt1)
	{
		for(int i=2;i<=cnt1;i++)
		{
			m--;
			in(b[i].x,b[1].x);
			// ans+=b[i].y*b[1].y;
		}
	}
	else
	{
		for(int i=cnt2-1;i>0;i--)
		{
			m--;
			in(c[cnt2].x,c[i].x);
			// ans+=c[cnt2].y*c[i].y;
		}
	}
	for(int i=1;i<=n;i++)add(i);
	int x,y,z;
	// cout<<"B"<<ans<<'\n';

	// for(auto i:s)
	// {
	// 	cout<<i.first<<' '<<i.second<<'\n';
	// }
	while(!q.empty()&&m)
	{
		x=q.top().f,y=q.top().t,z=q.top().w;
		q.pop();
		if(g(x,y))continue;
		in(x,y);
		// ans+=a[x]*a[y];
		add(x),add(y);
		m--;
	}	
	// cout<<m<<'\n';
	// if(s.size()!=m1)assert(0);
	ans=0;
	for(auto i:s)
	{
		ans+=a[i.first]*a[i.second];
	}
	cout<<ans<<'\n';
	for(auto i:s)
	{
		cout<<i.first<<' '<<i.second<<'\n';
	}
}