#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#define int long long
using namespace std;
const int MAXN = 1e6 + 5;
int n,m;
int a[MAXN];
vector<int> edge[MAXN];
pair<int,int> node[MAXN];
int flag = 0;
int build(){//构建生成树
    for(int i = 1; i <= n; i++){
        node[i].first = a[i];
        node[i].second = i;
    }
    sort(node + 1,node + 1 + n);
    int pos = 0;
    for(int i = 1; i <= n; i++){
        if(node[i].first >= 0){
            pos = i;
            break;
        }
    }
    int ans = 0;
    if(pos == 0){
        for(int i = n - 1; i >= 1; i--){
            edge[node[n].second].push_back(node[i].second);
            ans += node[n].first * node[i].first;
        }
        flag = 1;
        return ans;
    }
    if(node[1].first >= 0 || (node[1].first < 0 && node[2].first >= 0)){
        for(int i = 2; i <= n; i++){
            edge[node[1].second].push_back(node[i].second);
            ans += node[1].first * node[i].first;
        }
    }
    else{
        for(int i = pos; i <= n; i++){
            edge[node[1].second].push_back(node[i].second);
            ans += node[1].first * node[i].first;
        }
        for(int i = 2; i < pos; i++){
            edge[node[n].second].push_back(node[i].second);
            ans += node[n].first * node[i].first;
        }
    }
    return ans;
}
vector<pair<int,int> > up,down;
int s1,s2;
int rebuild(int dx){//连符号不同的叶子
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
    int res = 0;
    up.clear();
    down.clear();
    int pos = 0;
    for(int i = 1; i <= n; i++){
        if(node[i].first >= 0){
            pos = i;
            break;
        }
    }
    down.push_back({114,114});
    up.push_back({114,114});
    for(int i = 1; i < pos; i++){
        down.push_back({node[i].first,node[i].second});
    }
    for(int i = n; i >= pos; i--){
        up.push_back({node[i].first,node[i].second});
    }
    int size1 = up.size() - 1;
    int size2 = down.size() - 1;
    s1 = size1;
    s2 = size2;
    int whle = 0;
    while(1){//类似于归并操作
        int l1 = 2,l2 = 2;
        if(l1 + whle <= size1){
            l1 += whle;
        }
        if(l2 + whle <= size2){
            l2 += whle;
        }
        int l11 = l1,l22 = l2;
        if(l2 + 1 <= size2){
            q.push({up[l1].first * down[l2 + 1].first,2});
        }
        if(l1 + 1 <= size1){
            q.push({up[l1 + 1].first * down[l2].first,1});
        }
        if(l1 != 1 || l2 != 1){
            edge[up[l1].second].push_back(down[l2].second);
            dx -= 1;
            res += up[l1].first * down[l2].first;
        }
        if(dx <= 0){
            return res;
        }
        while(!q.empty()){
            pair<int,int> temp = q.top();
            q.pop();
            if(dx <= 0){
                return res;
            }
            if(temp.second == 1){
                l1 += 1;
                edge[down[l22].second].push_back(up[l1].second);
                dx -= 1;
                res += up[l1].first * down[l22].first;
                if(dx <= 0){
                    return res;
                }
                if(l1 + 1 <= size1){
                    q.push({up[l1 + 1].first * down[l22].first,1});
                }
            }
            else{
                l2 += 1;
                edge[up[l11].second].push_back(down[l2].second);
                dx -= 1;
                res += up[l11].first * down[l2].first;
                if(dx <= 0){
                    return res;
                }
                if(l2 + 1 <= size2){
                    q.push({up[l11].first * down[l2 + 1].first,2});
                }
            }
        }
        whle += 1;
    }
    return res;
}
int repro(int dx){//处理连了会减小贡献的边
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
    int whle = 0;
    while(1){//对正点负点的极值依次连(最大最小,次大次小,次次大次次小.......)
        int l1 = 1,l2 = 1;
        int l11 = l1,l22 = l2;
        int res = 0;
        up.clear();
        down.clear();
        int pos = 0;
        for(int i = 1; i <= n; i++){
            if(node[i].first >= 0){
                pos = i;
                break;
            }
        }
        down.push_back({114,114});
        up.push_back({114,114});
        down.push_back({node[n - l1 + 1].first,node[n - l1 + 1].second});
        up.push_back({node[l1].first,node[l1].second});
        for(int i = 1 + l1; i < pos; i++){
            down.push_back({node[i].first,node[i].second});
        }
        for(int i = n - l1; i >= pos; i--){
            up.push_back({node[i].first,node[i].second});
        }
        int size1 = up.size() - 1;
        int size2 = down.size() - 1;
        if(l2 + 1 <= size2){
            q.push({up[l1].first * down[l2 + 1].first,2});
        }
        if(l1 + 1 <= size1){
            q.push({up[l1 + 1].first * down[l2].first,1});
        }
        while(!q.empty()){
            pair<int,int> temp = q.top();
            q.pop();
            if(dx <= 0){
                return res;
            }
            if(temp.second == 1){
                l1 += 1;
                edge[down[l22].second].push_back(up[l1].second);
                dx -= 1;
                res += up[l1].first * down[l22].first;
                if(dx <= 0){
                    return res;
                }
                if(l1 + 1 <= size1){
                    q.push({up[l1 + 1].first * down[l22].first,1});
                }
            }
            else{
                l2 += 1;
                edge[up[l11].second].push_back(down[l2].second);
                dx -= 1;
                res += up[l11].first * down[l2].first;
                if(dx <= 0){
                    return res;
                }
                if(l2 + 1 <= size2){
                    q.push({up[l11].first * down[l2 + 1].first,2});
                }
            }
        }
    }
}
int vis[MAXN];
void print(){
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < edge[i].size(); j++){
            cout << i << " " << edge[i][j] << endl;
        }
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    int res = build();
    if(!(m ^ n - 1)){//树的情况
        cout << res << endl;
        print();
    }
    else{
        int temp = m - n + 1;
        int cnt1 = 0,cnt2 = 0;
        for(int i = 1; i <= n; i++){
            if(node[i].first < 0){
                cnt1 += 1;
            }
            else{
                cnt2 += 1;
            }
        }
        int base = (cnt1 - 1) * (cnt2 - 1);//连满不同符号叶子的边数
        if(!(base ^ temp)){//恰好剩连满叶子的边数
            res += rebuild(temp);
            cout << res << endl;
            print();
        }
        else if(base < temp){//需要连正边
            res += rebuild(base);
            int dx = temp - base;
            res += repro(dx);
            cout << res << endl;
            print();
        }
        else{//叶子边连不满
            res += rebuild(temp);
            cout << res << endl;
            print();
        }
        return 0;
    }
    return 0;
}