На числовой прямой заданы \(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\)
Система из трёх вложенных отрезков Выходные данные
Для каждого набора входных данных выведите \(n + 1\) строку: в первой из них выведите вес составленной системы, а в последующих \(n\) строках ровно по два числа — номера точек, являющихся границами отрезка с номером \(i\) (\(1 \le i \le n\)). Порядок вывода концов отрезка не важен — вы можете вывести как сначала левый, а затем правый конец, так и наоборот.
Если способов составить систему вложенных отрезков с минимальным весом несколько, выведите любой из них.
Примечание
Первый набор входных данных совпадает с примером из условия. Можно показать, что вес составленной системы является минимальным.
Во втором наборе входных данных есть всего \(6\) точек, поэтому необходимо использовать каждую из них, чтобы составить \(3\) отрезка.
| № | Входные данные | Выходные данные |
|
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
|
12
2 6
5 1
7 8
10
1 6
5 2
3 4
-6
5 1
4 2
|