// Arup Guha
// 9/23/2013
// Solution to 2010 ACPC Problem I: The Cyber Traveling Salesman

import java.util.*;

public class i {

	public static int n;
	public static int bridgeCost;
	public static pt[] cities;
	public static int[][] adj;

	public static void main(String[] args) {

		Scanner stdin = new Scanner(System.in);
		int loop = 1;
		n = stdin.nextInt();
		bridgeCost = stdin.nextInt();

		while (n != 0) {

			cities = new pt[n];

			// Read in cities
			for (int i=0; i<n; i++) {
				int x = stdin.nextInt();
				int y = stdin.nextInt();
				cities[i] = new pt(x,y);
			}

			// Read in adjacency matrix.
			adj = new int[n][n];
			for (int i=0; i<n; i++)
				for (int j=0; j<n; j++)
					adj[i][j] = stdin.nextInt();

			// Get best cost.
			int[] perm = new int[n];
			boolean[] used = new boolean[n];
			System.out.println(loop+". "+getMinCost(perm, used, 0));

			// Get next case.
			n = stdin.nextInt();
			bridgeCost = stdin.nextInt();
			loop++;
		}
	}

	public static int getMinCost(int[] perm, boolean[] used, int k) {

		// Just evaluate.
		if (k == n)
			return getCost(perm);

		int ans = Integer.MAX_VALUE;

		// Try each possible slot next.
		for (int i=0; i<n; i++) {
			if (!used[i]) {
				perm[k] = i;
				used[i] = true;
				int temp = getMinCost(perm, used, k+1);
				if (temp < ans)
					ans = temp;
				used[i] = false;
			}
		}

		return ans;
	}

	// Evaluate the input permutation.
	public static int getCost(int[] perm) {

		// Get baseline cost...
		int cost = 0;
		for (int i=0; i<n; i++)
			cost += adj[perm[i]][perm[(i+1)%n]];

		// Set up line segment intersection check.
		ArrayList<pt> intersections = new ArrayList<pt>();
		segment[] roads = new segment[n];
		for (int i=0; i<n; i++)
			roads[i] = new segment(cities[perm[i]], cities[perm[(i+1)%n]]);

		// Just do brute force here, going through each pair of non-adjacent line segments.
		for (int i=0; i<n; i++) {
			for (int j=i+2; j<n; j++) {
				if (j-i != n-1) {
					pt cross = roads[i].intersect(roads[j]);
					if (cross != null)
						intersections.add(cross);
				}
			}
		}

		// Makes it easier to see what's equal.
		Collections.sort(intersections);
		int cur = 1;
		for (int i=1; i<intersections.size(); i++) {

			// This is another of the same point.
			if (intersections.get(i).compareTo(intersections.get(i-1)) == 0)
				cur++;

			// Process the points we just iterated over.
			else {
				int tmp = cur*bridgeCost;
				cost += tmp;
				cur = 1;
			}
		}

		// Add in the last bit.
		if (intersections.size() > 0)
			cost += cur*bridgeCost;

		return cost;
	}
}

class pt implements Comparable<pt> {

	public double x;
	public double y;

	public pt (double myx, double myy) {
		x = myx;
		y = myy;
	}

	public static pt getVect(pt start, pt end) {
		return new pt(end.x-start.x, end.y-start.y);
	}

	// Compare to (to sort by x then y) with tolerances.
	public int compareTo(pt other) {
		if (this.x < other.x - 1e-9) return -1;
		if (this.x > other.x + 1e-9) return 1;
		if (this.y < other.y - 1e-9) return -1;
		if (this.y > other.y + 1e-9) return 1;
		return 0;
	}
}

class segment {

	public pt p1;
	public pt p2;
	public pt dir;

	public segment(pt start, pt end) {
		p1 = start;
		p2 = end;
		dir = pt.getVect(p1,p2);
	}

	public static double det(double a, double b, double c, double d) {
		return a*d - b*c;
	}

	public pt intersect(segment other) {

		// Set up determinants to solve for intersection.
		double a = dir.x; double b = -other.dir.x;
		double c = dir.y; double d = -other.dir.y;
		double e = other.p1.x - this.p1.x; double f = other.p1.y - this.p1.y;

		double den = segment.det(a,b,c,d);

		// Parallel case.
		if (Math.abs(den) < 1e-9) return null;

		// Doesn't intersect with this segment.
		double lambda = segment.det(e,b,f,d)/den;
		if (lambda < 0 || lambda > 1) return null;

		// Doesn't intersect with the other segment.
		double beta = segment.det(a,e,c,f)/den;
		if (beta < 0 || beta > 1) return null;

		// This is our intersection point.
		return new pt(p1.x+lambda*dir.x, p1.y+lambda*dir.y);
	}
}