1650C. Weight of the System of Nested Segments

1650C. Weight of the System of Nested Segments

C. Weight of the System of Nested Segments

• time limit per test2 seconds
• memory limit per test256 megabytes
• inputstandard input
• outputstandard output

On the number line there are m points, i-th of which has integer coordinate x${}_i\_i$ and integer weight w${}_i\_i$. The coordinates of all points are different, and the points are numbered from 1 to m.

在数字行上有M点，其中i具有整数坐标席x${}_i\_i$和整数加权w${}_i\_i$。所有点的坐标都不同，点的编号从1到m。

A sequence of n segments [l${}_1\_1$,r${}_1\_1$],[l${}_2\_2$,r${}_2\_2$],…,[l${}_n\_n$,r${}_n\_n$] is called system of nested segments if for each pair i,j (1≤i<j≤n) the condition l${}_i\_i$<l${}_j\_j$<r${}_j\_j$<r${}_i\_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.

n段[l${}_1\_1$,r${}_1\_1$],[l${}_2\_2$,r${}_2\_2$],…,[l${}_n\_n$,r${}_n\_n$]的序列称为嵌套段系统，如果每对i，j（1≤i<j≤n） 满足条件l${}_i\_i$<l${}_j\_j$<r${}_j\_j$<r${}_i\_i$。换句话说，第二段严格在第一段内，第三段严格在第二段内，依此类推。

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

对于给定的数字n，找到一个嵌套段系统，以便：

• both ends of each segment are one of m given points;

• 每段的两端是m个给定点中的一个；

• the sum of the weights 2⋅n of the points used as ends of the segments is minimal.

• 权重之和为2⋅n个用作线段端点的点是最小的。

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:

例如，设m=8。给定的点在图片中标记，它们的权重用红色标记，坐标用蓝色标记。创建一个由三个嵌套段组成的系统：

• weight of the first segment: 1+1=2

• 第一段的重量：1+1=2

• weight of the second segment: 10+(−1)=9

• 第二节重量：10+(−1)=9

• weight of the third segment: 3+(−2)=1

• 第三节重量：3+(−2)=1

• sum of the weights of all the segments in the system: 2+9+1=12

• 系统中所有段的权重之和：2+9+1=12 System of three nested segments

Input

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

输入数据的第一行包含一个整数t（1≤T≤10${}^4^4$）-输入测试用例的数量。

An empty line is written before each test case.

在每个测试用例之前写一行空行。

The first line of each test case contains two positive integers n (1≤n≤10${}^5^5$) and m (2⋅n≤m≤2⋅10${}^5^5$).

每个测试用例的第一行包含两个正整数n（1≤N≤10${}^5^5$）和m（2⋅N≤M≤2.⋅10${}^5^5$).

The next m lines contain pairs of integers x${}_i\_i$ (−10${}^9^9$≤xi≤10${}^9^9$) and w${}_i\_i$ (−10${}^4^4$≤wi≤10${}^4^4$) — coordinate and weight of point number i (1≤i≤m) respectively. All x${}_i\_i$ are different.

下一行M包含整数对x${}_i\_i$（−10${}^9^9$≤xi≤10${}^9^9$）和w${}_i\_i$(−10${}^4^4$≤wi≤10${}^4^4$）-点编号i的坐标和权重（1≤i≤m） 分别。所有x${}_i\_i$不同。

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

保证所有测试用例的m值之和不超过2⋅10${}^5^5$

Output

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≤i≤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.

对于每个测试用例，输出n+1行：在第一行中，输出合成系统的权重，在接下来的n行中，正好输出两个数字——第i段（1）端点的点的索引≤我≤n） 。输出线段端点的顺序并不重要——可以先输出左端点的索引，然后输出右端点的编号，或者反过来。

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

如果有几种方法可以使嵌套段的系统重量最小，请输出其中任何一种方法。

Example

input

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

output

12
2 6
5 1
7 8

10
1 6
5 2
3 4

-6
5 1
4 2

Note

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个点，所以您需要使用它们中的每一个来组成3个部分。

Solution

Code