Moonlit Tree Restoration

Little Yan is a fairy living on the Moon. To keep in touch with the human world, she planted a special tree by the riverside. When the moonlight passes through its branches and leaves and casts a particular pattern on the river, she can feel a deep spiritual connection with a certain human. Using magic, Little Yan had once interwoven the branches in a beautiful fashion. You may think of this tree as an undirected, connected graph with n nodes and m edges, with no self-loops and no multiple edges.

One day, after a business trip, Little Yan returned to the Moon to find that all the branches had been destroyed. In order to quickly restore the connection with the human world, she must use magic to reconnect the n nodes. The cost to magically create an edge (u, v) is determined by the product of the influence factors of the two endpoints, i.e. $$a_u \times a_v$$. Since Little Yan has forgotten the original shape of the tree, she is satisfied with any original valid configuration. In other words, you are to construct an undirected connected graph with m edges (with no self-loops and no multiple edges) on the n nodes such that the sum of the edge costs, where the cost of an edge (u, v) is $$a_u \times a_v$$, is minimized.

Input: The first line contains two integers n and m. The second line contains n integers, where the i-th integer is the influence factor $$a_i$$ of node i.

Note: It is guaranteed that the input values satisfy n-1 \le m \le \frac{n(n-1)}{2} so that at least one connected graph exists.

inputFormat

The first line contains two space‐separated integers n and m representing the number of nodes and edges respectively. The second line contains n space‐separated integers: a₁, a₂, …, a_n, where a_i denotes the influence factor of node i.

Constraints:
    2 \le n \le 2000
    n-1 \le m \le \frac{n(n-1)}{2}
    1 \le a_i \le 10^6

outputFormat

Output the minimum possible total cost on the first line. Then output exactly m lines, each containing two integers u and v (1-indexed), representing an edge between nodes u and v in your constructed graph. If there are multiple answers, output any one of them.

sample

3 2
1 2 3

5
1 2
1 3