「CROI · R2」落月摇情

>昨夜闲潭梦落花，\ 可怜春半不还家。\ >江水流春去欲尽，\ 江潭落月复西斜。 > >斜月沉沉藏海雾，\ 碣石潇湘无限路。\ >不知乘月几人归，\ 落月摇情满江树。

小烟是住在月亮上的仙女。为了和人间保持联系，小烟在江边种了一棵树。每当月光透过枝叶洒在江面上，形成特定的图案时，小烟就能与那个人产生心灵感应。为了让形成的图案更加美观，小烟用魔法让树的枝条互相交错成他喜欢的样子。你可以认为这棵树是一个**有 $n$ 个节点、$m$ 条边且无重边、无自环的无向连通图**。 某次小烟出差回到月亮上，发现这棵树上所有的枝条都被破坏了。为了快速恢复和人间的联系，小烟需要施加魔法将 $n$ 个节点重新连接起来。施加魔法生成一条边的代价与这条边对月光投影的影响程度有关。由于小烟忘记了原本树的形态，所以她希望花费最小的代价将这棵树恢复到任意一个可能的原先形态。也就是说，她需要这 $n$ 个节点之间形成一张有 $m$ 条边且无重边、无自环的无向连通图。 考虑到你不是仙女，很难计算每条边对投影的影响程度，善良的小烟给出了一个简单的计算方法：给你每个点的影响程度 $a_i$，则用魔法生成一条边 $(u,v)$ 的代价为 $a_u\times a_v$。请你帮小烟找到一组花费代价最小的施加魔法的方案。 **形式化地**，给出 $n$ 个点，每个点有点权 $a_i$，你需要构造一张有 $m$ 条边，且无重边、无自环的无向图，使得这 $n$ 个点连通。设边 $(u,v)$ 的权值为 $a_u\times a_v$，你需要最小化图中所有边的权值和。

输入共两行。 第一行两个非负整数 $n,m$。 第二行 $n$ 个由空格隔开的整数 $a_i$。

输出 $m+1$ 行。 第一行一个整数 $ans$，表示你构造的图中，所有边的权值和。 接下来的 $m$ 行每行两个正整数 $u,v$，表示你构造的图中存在一条边 $u,v$。你需要保证 $u\neq v$，且不存在两个无序二元组 $(u,v)$ 相同，且所有输出能表示一张 $n$ 个点的连通图。**如有多解，输出任意一组合法解即可**。

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

**【Special Judge】** 本题采用 Special Judge。只要你输出的图满足无重边、无自环且连通，同时其边权和与你输出的答案一致且输出的答案与标准答案一致，你就可以通过对应的测试点。 需要注意的是，请确保你的输出符合输出格式中的要求，否则你得到的结果可能不确定。 本题开启子任务依赖。你可以得到一个子任务对应的分数，当且仅当你通过了当前子任务，同时你也通过了当前子任务依赖的所有子任务。具体的依赖情况见“数据范围”部分的表格。 **【数据范围】** 对于所有数据，满足 $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$。 本题开启捆绑测试、开启子任务依赖。 | 子任务编号 | $n \le$ | $m \le$ | 特殊性质 | 分值 |子任务依赖| | :----------: | :-----: | :--------------: | :------------: | :-----: | :-----: | |$1$ |$7$ | $21$ | 无 |$10$| 无 | | $2$ | $16$ | $120$ | 无 |$15$| $1$ | | $3$ | $1000$ | $3\times 10^5$| 无 |$15$|$1,2$| | $4$ | $2\times 10^5$ | $3\times 10^5$ | 保证 $a_i$ 为非负整数 |$15$|无| | $5$ | $2\times 10^5$ | $3\times 10^5$ | 保证 $m=n-1$ |$10$|无| | $6$ | $2\times 10^5$ | $3\times 10^5$ | 无 | $15$|$1,2,3$| | $7$ | $10^6$ | $10^6$ | 无 | $20$|$1,2,3,6$| **【样例解释】** - 对于样例一，构造出的图如下图所示。边权和为 $2+-2+-4+-3+-6=-13$。该样例的构图方式是唯一的。  - 对于样例二，构造出的图如下图所示。边权和为 $-3+-6+-12+-15+0=-36$。该样例还存在其它正确的构图方式，比如你可以把边 $(5,6)$ 改为边 $(5,3)$。