D. Шичикуджи и электросеть
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Шичикуджи — новое местное божество Южного Храма Черной Улитки. Ее первое задание заключается в следующем:

В префектуре 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|$$$ км.

Шичикуджи хочет осуществить эту затею, потратив как можно меньше денег, так как она считает, что нет ничего важнее в мире, чем деньги. Однако она умерла, когда была всего в пятом классе (разумеется, божества не стареют после смерти), поэтому недостаточно смышленая, чтобы воплотить проект в жизнь. Поэтому она просит вас о помощи.

Таким образом, от вас требуется предоставить Шичикуджи следующую информацию: минимальное количество иен, необходимое, чтобы обеспечить электричеством все города, города, в которых будут построены электростанции, и проведенные соединения.

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

Входные данные

В первой строке записано одно целое число $$$n$$$ ($$$1 \leq n \leq 2000$$$) — количество городов.

Затем следует $$$n$$$ строк. В $$$i$$$-й строке записаны два целых числа $$$x_i$$$ ($$$1 \leq x_i \leq 10^6$$$) и $$$y_i$$$ ($$$1 \leq y_i \leq 10^6$$$) — координаты $$$i$$$-го города.

В следующей строке записаны $$$n$$$ целых чисел $$$c_1, c_2, \dots, c_n$$$ ($$$1 \leq c_i \leq 10^9$$$) — цена установки электростанции в $$$i$$$-м городе.

В последней строке записаны $$$n$$$ целых чисел $$$k_1, k_2, \dots, k_n$$$ ($$$1 \leq k_i \leq 10^9$$$).

Выходные данные

В первой строке выведите одно целое число, обозначающее минимальное количество иен, требуемых для конструкции.

Затем выведите одно целое число $$$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
1 1
3 2
3 2 3
3 2 3
Выходные данные
8
3
1 2 3 
0
Входные данные
3
2 1
1 2
3 3
23 2 23
3 2 3
Выходные данные
27
1
2 
2
1 2
2 3
Примечание

Для ответов на примеры смотрите на данные графики (города с электростанциями раскрашены зеленым, остальные — синим, кабели покрашены в красный):

В первом примере цена строительства электростанций во всех городах равна $$$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 иен.