У світлі демографічного вибуху населення Землі, будується ряд міст на Місяці. Ми б хотіли щоб Ви нам допомогли у визначенні кращої мережі доріг між цими містами. Враховуючи високі затрати, пов'язані з будівництвом доріг на Місяці, усі дороги утворюють цикл, починаючи від міста, яке появиться на Місяці першим, проходить через усі інші міста рівно один раз (але у довільному порядку) і завершується у першому (Так, це видозміненая задача бродячого продавця). У Вас є інформація про витрати на будівництво дороги міжу кожною парою міст. Дороги є односторонніми, але витрати на будівництво дороги від міста \textbf{i} до \textbf{j} такі ж, як на будівництво дороги від міста \textbf{j} до \textbf{i}. Коли дороги перетинаються у місці, яке не є містом, необхіно враховувати витрати на будівництво об'їздного моста. Будівництво об'їздного моста визначається як вартість системи \textbf{k·(k-1)·C/2}, де \textbf{k --} кількість доріг, які перетинаються у цьому місці, а \textbf{C} - задана постійна. Слід відмітити, що міста розміщено так, що ніякі три міста не розміщені на одній прямій. \InputFile Вашу програму буде апробовано на одному чи декількох тестах. Кожен тест задається при допомозі \textbf{2·N+1} рядків. У першому рядку кожного тесту вказано два цілих числа: (\textbf{2} < \textbf{N} < \textbf{9}) -- кількість міст та (\textbf{0} < \textbf{C} ≤ \textbf{1000000}) - коефіцієнт, який використовується при визначенні вартості будівництва мостів. Після цього йдуть рядки з декартовими координатами міст, вказані по порядку. Кожне місто задано у окремому рядку двома цілими числами: \textbf{x_i} та \textbf{y_i} де (\textbf{-1000} ≤ \textbf{x_i}, \textbf{y_i} ≤ \textbf{1000}). Ніякі два міста не розміщено на одному і тому ж (\textbf{x}, \textbf{y}) місці. Останні \textbf{N} рядків тесту задають матрицю \textbf{N}×\textbf{N}, яка є вартістю будівництва дороги між двома містами. Матрицю задано при допомозі \textbf{N} рядків, кожен з яких містить \textbf{N} цілих чисел. \textbf{j}--е значення у \textbf{i}--му рядку, позначається як \textbf{c_ij} і є вартістю будівництва дороги від міста \textbf{i} до міста \textbf{j}, причому (\textbf{0} < \textbf{c_ij} ≤ \textbf{10^6}) і (\textbf{c_ij} = \textbf{c_ji}) і (\textbf{c_ii} = \textbf{0}). Завершає тестові дані рядок з двома нулями. \OutputFile Для кожного теста вивести наступний рядок: \textbf{k. M} де \textbf{k} -- номер тесту (починаюи з одиниці), а \textbf{M} - мінімальна вартість створення дорожньої мережі. \includegraphics{https://static.e-olymp.com/content/19/1931f7ec74076cbd80441c6958d0d8b08bd90a59.jpg}