На числовой прямой заданы \(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
|