Problem Background

Last night, in the quiet pool, dreams of falling flowers,\
Alas, the mid-spring has come, yet I haven't returned home.\
The river water flows, taking the spring away,\
The moon falls over the river pool, slanting westward again.

The slanting moon hides deep in the sea mist,\
Endless paths between Jieshi and Xiaoxiang.\
I wonder how many return under the moon,\
The moon shakes emotions, full over the river trees.

Problem Description

Xiaoyan is a fairy living on the moon. To stay connected with the human world, Xiaoyan planted a tree by the riverside. Whenever moonlight filters through the branches and leaves, forming a specific pattern on the river surface, Xiaoyan can establish a telepathic connection with that person. To make the formed pattern more aesthetically pleasing, Xiaoyan uses magic to intertwine the branches into a shape she likes. You can consider this tree as an undirected connected graph with $n$ nodes and $m$ edges, without multiple edges or self-loops.

One time, after returning from a business trip back to the moon, Xiaoyan found that all the branches on this tree were destroyed. To quickly restore the connection with the human world, Xiaoyan needs to cast a spell to reconnect the $n$ nodes. The cost of casting a spell to create an edge is related to the impact of this edge on the moonlight projection. Since Xiaoyan has forgotten the original form of the tree, she hopes to restore it to any possible original state with the least cost. That is, she needs to form an undirected connected graph with $m$ edges, without multiple edges or self-loops, among these $n$ nodes.

Considering that you are not a fairy and it's hard to calculate the impact of each edge on the projection, the kind Xiaoyan provides a simple calculation method: she gives you the impact degree $a_i$ of each node, then the cost of casting a spell to create an edge $(u, v)$ is $a_u \times a_v$. Please help Xiaoyan find a spell casting scheme with the minimum cost.

Formally, given $n$ nodes, each with a node weight $a_i$, you need to construct an undirected graph with $m$ edges, without multiple edges or self-loops, such that these $n$ nodes are connected. Let the weight of edge $(u, v)$ be $a_u \times a_v$, you need to minimize the sum of the weights of all edges in the graph.

Input Format

The input consists of two lines.

The first line contains two non-negative integers $n$ and $m$.

The second line contains $n$ integers separated by spaces, $a_i$.

Output Format

Output $m+1$ lines.

The first line contains an integer $ans$, representing the sum of the weights of all edges in the graph you constructed.

The next $m$ lines each contain two positive integers $u$ and $v$, indicating that there is an edge $u, v$ in the graph you constructed. You need to ensure $u \neq v$, and there are no two identical unordered pairs $(u, v)$, and all outputs can represent a connected graph of $n$ nodes. If there are multiple solutions, output any valid solution.

Sample Input and Output

Sample Input #1

4 5
1 2 -2 -3

Sample Output #1

-13
1 2
1 3
1 4
2 3
2 4

Sample Input #2

6 5
1 2 4 5 0 -3

Sample Output #2

-36
1 6
2 6
3 6
4 6
5 6

Notes

[Special Judge]

This problem uses a Special Judge. As long as your output graph is without multiple edges, self-loops, and is connected, and its edge weight sum matches your output answer and the standard answer, you can pass the corresponding test point.

Note that ensure your output meets the requirements in the output format, otherwise, the result may be uncertain.

This problem has subtask dependencies. You can get the score for a subtask if and only if you pass the current subtask and all the subtasks it depends on. See the "Data Range" section for specific dependencies.

[Data Range]

For all data, it satisfies $1 \leq n \leq 10^6$, $n-1 \leq m \leq \min(10^6, \frac{n(n-1)}{2})$, $0 \leq |a_i| \leq 10^6$.

This problem has bundled testing and subtask dependencies enabled.

[Sample Explanation]

• For Sample #1, the constructed graph is shown below. The sum of edge weights is $2 + -2 + -4 + -3 + -6 = -13$. This sample's graph construction method is unique.

• For Sample #2, the constructed graph is shown below. The sum of edge weights is $-3 + -6 + -12 + -15 + 0 = -36$. This sample also has other correct graph construction methods, such as changing edge $(5, 6)$ to edge $(5, 3)$.

见题面 Input 部分

见题面 Output 部分