数轴上有 $$$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 < j \le n$$$) 条件 $$$l_i < l_j < r_j < r_i$$$ 很满意。换句话说,第二个片段严格位于第一个片段内部,第三个片段严格位于第二个片段内部,依此类推。
对于给定的数字$$$n$$$,找到一个嵌套段系统,使得:
- 每段的两端都是 $$$m$$$ 给定点之一;
- 用作线段末端的点的权重 $$$2\cdot n$$$ 之和最小。
例如,令 $$$m = 8$$$。给定的点在图中被标记,它们的权重被标记为红色,它们的坐标被标记为蓝色。创建一个由三个嵌套段组成的系统:
- 第一段的权重:$$$1 + 1 = 2$$$
- 第二段的权重:$$$10 + (-1) = 9$$$
- 第三段的权重:$$$3 + (-2) = 1$$$
- 系统中所有段的权重总和:$$$2 + 9 + 1 = 12$$$
三个嵌套段系统
输入
输入数据的第一行包含一个整数 $$$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$$$。
输出
对于每个测试用例,输出 $$$n + 1$$$ 行:在第一行中,输出组合系统的权重,在接下来的 $$$n$$$ 行中输出恰好两个数字 — 作为第 $$$i$$$ 段端点的点的索引 ($$$1 \le i \le n$$$)。输出线段端点的顺序并不重要——您可以先输出左端点的索引,然后输出右端点的编号,或者反之亦然。
如果有多种方法可以构建具有最小权重的嵌套段系统,请输出其中任何一种。
示例
输入 #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
注意
第一个测试用例与条件示例一致。可以看出,所组成的系统的重量是最小的。
第二个测试用例只有 $$$6$$$ 点,因此您需要使用它们中的每一个来组成 $$$3$$$ 段。