C. Вес системы вложенных отрезков
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На числовой прямой заданы $$$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$$$). Порядок вывода концов отрезка не важен — вы можете вывести как сначала левый, а затем правый конец, так и наоборот.

Если способов составить систему вложенных отрезков с минимальным весом несколько, выведите любой из них.

Пример
Входные данные
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
Выходные данные
12
2 6
5 1
7 8

10
1 6
5 2
3 4

-6
5 1
4 2
Примечание

Первый набор входных данных совпадает с примером из условия. Можно показать, что вес составленной системы является минимальным.

Во втором наборе входных данных есть всего $$$6$$$ точек, поэтому необходимо использовать каждую из них, чтобы составить $$$3$$$ отрезка.