Кибер-коммивояжер

В свете демографического взрыва населения Земли, строится ряд городов на Луне. Мы бы хотели чтобы Вы нам помогли в определении лучшей дорожной сети между этими городами. Учитывая высокие затраты, связанные со строительством дорог на Луне, все дороги образуют цикл, начиная от города, который появится на Луне первым, проходит через все другие города ровно один раз (но в любом произвольном порядке) и заканчивается в первом (Да, это видоизменённая задача бродячего торговца).

Вы имеете информацию о расходах на строительство дороги между каждой парой городов. Дороги являются односторонними, но расходы на строительство дороги от города i до j такие же, как на строительство дороги от города j до i. Когда дороги пересекаются в месте, которое не является городом, необходимо учитывать затраты на строительство объездного моста. Строительство объездного моста определяется как стоимость системы k·(k-1)·C/2, где k – количество дорог, пересекающихся в этом месте, и C - заданная постоянная.

Следует отметить, что города расположены так, что никакие три города не расположены на одной прямой.

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

Ваша программа будет опробована на одном или нескольких тестах. Каждый тест задается с помощью 2·N+1 строк. В первой строке каждого теста указывается два целых числа: (2 < N < 9) – количество городов и (0 < C ≤ 1000000) - коэффициент, используемый при определении стоимости строительства мостов.

После этого идут строки с декартовыми координатами городов, указанные по порядку. Каждый город задан в отдельной строке двумя целыми числами: x_i и y_i где (-1000 ≤ x_i, y_i ≤ 1000). Никакие два города не расположены на одном и том же (x, y) месте.

Последние N строк теста задают матрицу N×N, представляющую стоимость строительства дороги между двумя городами. Матрица задается с помощью N строк, каждая из которых содержит N целых чисел. j–е значения в i–й строке, обозначается как c_ij и является стоимостью строительства дороги от города i в город j, причём (0 < c_ij ≤ 10⁶) и (c_ij = c_ji) и (c_ii = 0).

Завершает тестовые данные строка с двумя нулями.

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

Для каждого теста, вывести следующую строку:

k. M

где k – номер теста (начиная с единицы), а M - минимальная стоимость создания дорожной сети.