| Codeforces Round 776 (Div. 3) |
|---|
| Закончено |
На числовой прямой заданы $$$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$$$ отрезка.
