Шичикуджи — новое местное божество Южного Храма Черной Улитки. Ее первое задание заключается в следующем:
В префектуре X построено \(n\) новых городов. Города пронумерованы от \(1\) до \(n\). Город \(i\) находится в \(x_i\) км на север от храма и в \(y_i\) ем на восток от храма. Возможно, что \((x_i, y_i) = (x_j, y_j)\) даже если \(i \ne j\).
Шичикуджи планирует обеспечить электричеством каждый город либо с помощью установки там электростанции, либо с помощью соединения его с другим городом, в котором уже есть электричество. То есть в городе есть электричество, если в нём есть электростанция или он соединён напрямую или по цепочке кабелей с городом, в котором есть электростанция.
- Возведение электростанции в городе \(i\) стоит \(c_i\) иен;
- Соединение города \(i\) и города \(j\) стоит \(k_i + k_j\) иен за каждый км кабеля, использованного для соединения. Однако кабель можно прокладывать вдоль сторон света (на север, юг, восток, запад). Кабели могут пересекать друг друга. У каждого кабеля оба конца должны быть в некоторых городах. Если город \(i\) и город \(j\) соединены кабелем, то кабель всегда будет прокладываться по кратчайшему пути из города \(i\) в город \(j\). Тогда длина кабеля, соединяющего город \(i\) и город \(j\), равна \(|x_i - x_j| + |y_i - y_j|\) км.
Шичикуджи хочет осуществить эту затею, потратив как можно меньше денег, так как она считает, что нет ничего важнее в мире, чем деньги. Однако она умерла, когда была всего в пятом классе (разумеется, божества не стареют после смерти), поэтому недостаточно смышленая, чтобы воплотить проект в жизнь. Поэтому она просит вас о помощи.
Таким образом, от вас требуется предоставить Шичикуджи следующую информацию: минимальное количество иен, необходимое, чтобы обеспечить электричеством все города, города, в которых будут построены электростанции, и проведенные соединения.
Если существует несколько способов так выбрать города и соединения, чтобы получить конструкцию минимальной цены, то выведите любую из них.
Выходные данные
В первой строке выведите одно целое число, обозначающее минимальное количество иен, требуемых для конструкции.
Затем выведите одно целое число \(v\) — количество электростанций, которые требуется построить.
Далее выведите \(v\) целых чисел, обозначающих номера городов, в которых требуется построить электростанции. Каждое число должно быть от \(1\) до \(n\) и все числа должны быть попарно различны. Можно выводить числа в произвольном порядке.
После этого выведите одно целое число \(e\) — количество необходимых соединений.
Наконец, выведите \(e\) пар целых чисел \(a\) и \(b\) (\(1 \le a, b \le n\), \(a \ne b\)), обозначающих, что между городами \(a\) и \(b\) будет проведено соединение. Каждая неупорядоченная пара городов может встречаться не более одного раза (для каждого \((a, b)\) не должно больше существовать пар \((a, b)\) или \((b, a)\)). Пары можно выводить в произвольном порядке.
Если существует несколько способов так выбрать города и соединения, чтобы получить конструкцию минимальной цены, то выведите любую из них.
Примечание
Для ответов на примеры смотрите на данные графики (города с электростанциями раскрашены зеленым, остальные — синим, кабели покрашены в красный):
В первом примере цена строительства электростанций во всех городах равна \(3 + 2 + 3 = 8\). Можно показать, что больше никакая конфигурация не стоит меньше 8 иен.
Во втором примере цена строительства электростанции в городе 2 равна 2. Стоимость соединения городов 1 и 2 равна \(2 \cdot (3 + 2) = 10\). Стоимость соединения городов 2 и 3 равна \(3 \cdot (2 + 3) = 15\). Поэтому итоговая цена равна \(2 + 10 + 15 = 27\). Можно показать, что никакая конфигурация не стоит меньше 27 иен.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2 3
1 1
3 2
3 2 3
3 2 3
|
8
3
1 2 3
0
|
|
2
|
3
2 1
1 2
3 3
23 2 23
3 2 3
|
27
1
2
2
1 2
2 3
|