CF1650C.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 \lt j \le n$) the condition $l_i \lt l_j \lt r_j \lt 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

数轴上有 $m$ 个点，其中第 $i$ 个点具有整数坐标 $x_i$ 和整数权重 $w_i$。所有点的坐标互不相同，且这些点编号为 $1$ 至 $m$。

一个由 $n$ 个区间 $[l_1, r_1], [l_2, r_2], \dots, [l_n, r_n]$ 构成的序列被称为嵌套区间系统，当且仅当对任意一对下标 $i, j$（满足 $1 \le i \lt j \le n$），均有 $l_i \lt l_j \lt r_j \lt r_i$ 成立。换言之，第二个区间严格包含于第一个区间内部，第三个区间严格包含于第二个区间内部，依此类推。

给定正整数 $n$，请找出一个嵌套区间系统，使得：

• 每个区间的两个端点均来自给定的 $m$ 个点；
• 所有 $2n$ 个被选作区间端点的点的权重之和最小。

例如，设 $m = 8$。图中用标记标出了给定的点，其权重以红色标出，坐标以蓝色标出。构造一个由三个嵌套区间组成的系统：

• 第一个区间的权重：$1 + 1 = 2$
• 第二个区间的权重：$10 + (-1) = 9$
• 第三个区间的权重：$3 + (-2) = 1$
• 该嵌套区间系统中所有区间的权重总和：$2 + 9 + 1 = 12$

三个嵌套区间的系统

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$.

输入数据的第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示输入测试用例的数量。

每个测试用例之前均有一空行。

每个测试用例的第一行包含两个正整数 $n$（$1 \le n \le 10^5$）和 $m$（$2 \cdot n \le m \le 2 \cdot 10^5$）。

接下来的 $m$ 行每行包含一对整数 $x_i$（$-10^9 \le x_i \le 10^9$）和 $w_i$（$-10^4 \le w_i \le 10^4$），分别表示第 $i$ 个点（$1 \le i \le m$）的坐标与权重。所有 $x_i$ 互不相同。

保证所有测试用例中 $m$ 的总和不超过 $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.

对于每个测试用例，输出 $n + 1$ 行：第一行输出组合系统的总重量；接下来的 $n$ 行中，每行恰好输出两个数——即第 $i$ 个线段（$1 \le i \le n$）的两个端点的索引。输出线段端点的顺序无关紧要——你可以先输出左端点的索引、再输出右端点的索引，也可以反过来。

如果存在多种方式构造具有最小总重量的嵌套线段系统，则输出其中任意一种即可。

The first test case coincides with the example from the condition. It can be shown that the weight of the composed system is minimal.

The second test case has only $6$ points, so you need to use each of them to compose $3$ segments.

第一个测试用例与题面中的示例一致。可以证明，所构成系统的总权重最小。

第二个测试用例仅有 $6$ 个点，因此你需要使用全部这 $6$ 个点来构成 $3$ 条线段。