A14916 | Weight of the System of Nested Segments

On the number line there are $m$ points, $i$ -th of which has integer coordinate $x_i$ and integer weight $w_i$ . The coordinates of all points are different, and the points are numbered from $1$ to $m$ .

A sequence of $n$ segments $[l_1, r_1], [l_2, r_2], \dots, [l_n, r_n]$ is called system of nested segments if for each pair $i, j$ ( $1 \le i < j \le n$ ) the condition $l_i < l_j < r_j < r_i$ is satisfied. In other words, the second segment is strictly inside the first one, the third segment is strictly inside the second one, and so on.

For a given number $n$ , find a system of nested segments such that:

- both ends of each segment are one of $m$ given points;
- the sum of the weights $2\cdot n$ of the points used as ends of the segments is minimal.

For example, let $m = 8$ . The given points are marked in the picture, their weights are marked in red, their coordinates are marked in blue. Make a system of three nested segments:

- weight of the first segment: $1 + 1 = 2$
- weight of the second segment: $10 + (-1) = 9$
- weight of the third segment: $3 + (-2) = 1$
- sum of the weights of all the segments in the system: $2 + 9 + 1 = 12$

System of three nested segments

The first line of input data contains an integer $t$ ( $1 \le t \le 10^4$ ) —the number of input test cases.

An empty line is written before each test case.

The first line of each test case contains two positive integers $n$ ( $1 \le n \le 10^5$ ) and $m$ ( $2 \cdot n \le m \le 2 \cdot 10^5$ ).

The next $m$ lines contain pairs of integers $x_i$ ( $-10^9 \le x_i \le 10^9$ ) and $w_i$ ( $-10^4 \le w_i \le 10^4$ ) — coordinate and weight of point number $i$ ( $1 \le i \le m$ ) respectively. All $x_i$ are different.

It is guaranteed that the sum of $m$ values over all test cases does not exceed $2 \cdot 10^5$ .

For each test case, output $n + 1$ lines: in the first of them, output the weight of the composed system, and in the next $n$ lines output exactly two numbers — the indices of the points which are the endpoints of the $i$ -th segment ( $1 \le i \le n$ ). The order in which you output the endpoints of a segment is not important — you can output the index of the left endpoint first and then the number of the right endpoint, or the other way around.

If there are several ways to make a system of nested segments with minimal weight, output any of them.