Weight of the System of Nested Segments

题意翻译

在一个数轴上，有一些整点。称一些数为 包含系统 ，当这些坐标配对 $(x_l,x_r)$时，任意 $i<j$ 有 $l_i<l_j<r_j<r_l$。 共有 $m$ 个点，取出其中 $2n$ 个点，使得这些数配对 $n$ 组后代价和最小。 一个配对的代价为 $w_l+w_r$。 给出每个点的坐标 $x$ 和代价 $w$。求最小代价和和匹配数字的序号（序号就是输入的顺序，从 $1$ 开始）。 $\sum n$ 不超过 $2\times 10^5$。

题目描述

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.

输入输出样例

输入样例 #1

3

3 8
0 10
-2 1
4 10
11 20
7 -1
9 1
2 3
5 -2

3 6
-1 2
1 3
3 -1
2 4
4 0
8 2

2 5
5 -1
3 -2
1 0
-2 0
-5 -3

输出样例 #1

12
2 6
5 1
7 8

10
1 6
5 2
3 4

-6
5 1
4 2

说明

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.