Description

Xiao Yan, a fairy living on the moon, maintains a magical tree by the river to communicate with the human world. Moonlight forms specific patterns through its branches on the river surface. To restore the tree after damage, Xiao Yan needs to reconnect its nodes with minimal cost. The tree is an undirected connected graph with $n$ nodes and $m$ edges, without multiple edges or self-loops.

The cost to generate an edge $(u,v)$ is calculated as $a_u \times a_v$, where $a_i$ represents the influence factor of node $i$. Your task is to find a connected graph with $m$ edges that minimizes the total edge cost.

Formally: Given $n$ nodes with weights $a_i$, construct a connected undirected graph with $m$ edges (no duplicates/self-loops) such that the sum of all edge weights ($a_u \times a_v$) is minimized.

Input Format

First line: Two non-negative integers $n$, $m$.
Second line: $n$ space-separated integers $a_i$.

Output Format

Output $m+1$ lines:

• First line: Total cost $ans$.
• Next $m$ lines: Pairs $u$ $v$ representing edges (unordered, no duplicates).
  Any valid solution is accepted if conditions are met.

4 5
1 2 -2 -3

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

6 5
1 2 4 5 0 -3

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

Hint

【Special Judge】
Your output will be accepted if:

• The graph is connected with no duplicate/self-loop edges.
• The total cost matches the claimed $ans$ (which must equal the standard answer).

【Data Range】
Constraints:

• $1 \leq n \leq 10^6$
• $n-1 \leq m \leq \min(10^6, \frac{n(n-1)}{2})$
• $|a_i| \leq 10^6$

Subtasks (with dependencies):
| Subtask | $n \leq$ | $m \leq$ | Special Conditions | Points | Dependencies | |---------|----------|----------|--------------------|--------|--------------| | 1 | 7 | 21 | None | 10 | None | | 2 | 16 | 120 | None | 15 | 1 | | 3 | 1000 | 3e5 | None | 15 | 1,2 | | 4 | 2e5 | 3e5 | $a_i \geq 0$ | 15 | None | | 5 | 2e5 | 3e5 | $m = n-1$ | 10 | None | | 6 | 2e5 | 3e5 | None | 15 | 1,2,3 | | 7 | 1e6 | 1e6 | None | 20 | 1,2,3,6 |

【Sample Explanations】

• Sample 1: Unique solution with total cost $-13$.
  
• Sample 2: Multiple valid solutions (e.g., edge $(5,6)$ can be replaced with $(5,3)$).