P10768 「CROI · R2」Moonlit Emotion

> He dreamed of flowers falling o'er the pool last night; > Alas! Spring has gone, he can’t homeward go. > The water bearing spring will run away in flight; > The moon over the pool will in the west sink low. > In the mist on the sea the slanting moon will hide. > It's a long way from northern hills to southern streams. > How many can go home by moonlight on the tide? > The setting moon sheds o'er riverside trees but dreams riverside trees.

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.

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

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.

**【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)$).