During the loading of the game "Dungeons and Candies" you are required to get descriptions of k levels from the server. Each description is a map of an n × m checkered rectangular field. Some cells of the field contain candies (each cell has at most one candy). An empty cell is denoted as "." on the map, but if a cell has a candy, it is denoted as a letter of the English alphabet. A level may contain identical candies, in this case the letters in the corresponding cells of the map will be the same.

<image>

When you transmit information via a network, you want to minimize traffic — the total size of the transferred data. The levels can be transmitted in any order. There are two ways to transmit the current level A:

  1. You can transmit the whole level A. Then you need to transmit n·m bytes via the network. 
  2. You can transmit the difference between level A and some previously transmitted level B (if it exists); this operation requires to transmit dA, B·w bytes, where dA, B is the number of cells of the field that are different for A and B, and w is a constant. Note, that you should compare only the corresponding cells of levels A and B to calculate dA, B. You cannot transform the maps of levels, i.e. rotate or shift them relatively to each other. 



Your task is to find a way to transfer all the k levels and minimize the traffic.

Input

The first line contains four integers n, m, k, w (1 ≤ n, m ≤ 10; 1 ≤ k, w ≤ 1000). Then follows the description of k levels. Each level is described by n lines, each line contains m characters. Each character is either a letter of the English alphabet or a dot ("."). Please note that the case of the letters matters.

Output

In the first line print the required minimum number of transferred bytes.

Then print k pairs of integers x1, y1, x2, y2, ..., xk, yk, describing the way to transfer levels. Pair xi, yi means that level xi needs to be transferred by way yi. If yi equals 0, that means that the level must be transferred using the first way, otherwise yi must be equal to the number of a previously transferred level. It means that you will transfer the difference between levels yi and xi to transfer level xi. Print the pairs in the order of transferring levels. The levels are numbered 1 through k in the order they follow in the input.

If there are multiple optimal solutions, you can print any of them.

Examples

Input

2 3 3 2
A.A
...
A.a
..C
X.Y
...


Output

14
1 0
2 1
3 1


Input

1 1 4 1
A
.
B
.


Output

3
1 0
2 0
4 2
3 0


Input

1 3 5 2
ABA
BBB
BBA
BAB
ABB


Output

11
1 0
3 1
2 3
4 2
5 1

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.PriorityQueue;

public class C {
	FastScanner in = new FastScanner(System.in);
	PrintWriter out = new PrintWriter(System.out);
	
	int n, m, k, w;
	int[][] edge;
	boolean[] visited;
	
	public class Kruskal {
		protected final static int INF = 1_000_000_000;
		
		class UnionFindTree {
			int[] parent;
			
			public UnionFindTree(int n) {
				parent = new int[n];
				for (int i = 0; i < parent.length; i++) {
					parent[i] = i;
				}
			}
			
			public int find(int x) {
				if (parent[x] == x) return x;
				return parent[x] = find(parent[x]);
			}
			
			public boolean same(int x, int y) {
				return find(x) == find(y);
			}
			
			public void unite(int x, int y) {
				int xx = find(x), yy = find(y);
				if (xx == yy) return;
				parent[xx] = yy;
			}
		}
		
		class State implements Comparable<State> {
			int x, y;
			
			State(int x, int y) {
				this.x = x;
				this.y = y;
			}

			public int compareTo(State s) {
				int c1 = edge[x][y], c2 = edge[s.x][s.y];
				if (c1 < c2) return -1;
				else if (c1 > c2) return 1;
				else return 0;
			}
		}
		
		int[][] edge;
		
		Kruskal(int[][] edge) {
			this.edge = edge;
		}
		
		KruskalResult doit() {
			int kN = edge.length;
			KruskalResult res = new KruskalResult(kN);
			
			UnionFindTree uft = new UnionFindTree(kN);
			PriorityQueue<State> pq = new PriorityQueue<State>();
			
			for (int i = 0; i < kN; i++) 
				for (int j = i + 1; j < kN; j++) 
					pq.add(new State(i, j));
			
			while (!pq.isEmpty()) {
				State s = pq.poll();
				if (uft.same(s.x, s.y)) continue;
				
				uft.unite(s.x, s.y);
				if (edge[s.x][s.y] * w < n * m)
					res.sum += edge[s.x][s.y] * w;
				else {
					res.sum += n * m;
					edge[s.x][s.y] = edge[s.y][s.x] = -1;
				}
				res.connected[s.x].add(s.y);
				res.connected[s.y].add(s.x);
			}
			
			return res;
		}
	}

	class KruskalResult {
		ArrayList<Integer>[] connected;
		int sum;
		
		@SuppressWarnings("unchecked")
		KruskalResult(int n) {
			connected = new ArrayList[n];
			for (int i = 0; i < n; i++)
				connected[i] = new ArrayList<Integer>();
		}
		
		@Override
		public String toString() {
			StringBuilder res = new StringBuilder();
			res.append("sum = " + sum + "\n");
			res.append("-------edges-------\n");
			for (int i = 0; i < connected.length; i++)
				res.append(Arrays.toString(connected[i].toArray(new Integer[0])) + "\n");
			
			return res.toString();
		}
	}
	
	void dfs(int n, int before, KruskalResult kres) {
		if (visited[n]) return;

		visited[n] = true;
		if (before != -1 && edge[n][before] == -1) out.println((n+1) + " 0");
		else out.println((n+1) + " " + (before+1));
		
		for (int i = 0; i < kres.connected[n].size(); i++) {
			int next = kres.connected[n].get(i);
			dfs(next, n, kres);
		}
	}
	
	public void run() {
		n = in.nextInt(); m = in.nextInt(); k = in.nextInt(); w = in.nextInt();
		
		char[][][] map = new char[k][n][];
		edge = new int[k][k];
		
		for (int i = 0; i < k; i++) {
			for (int y = 0; y < n; y++) {
				map[i][y] = in.next().toCharArray();
			}
		}
		
		for (int i = 0; i < k; i++) {
			for (int j = i + 1; j < k; j++) {
				for (int y = 0; y < n; y++) {
					for (int x = 0; x < m; x++) {
						if (map[i][y][x] != map[j][y][x]) {
							edge[i][j]++; 
						}
					}
				}
				edge[j][i] = edge[i][j];
			}
		}
		
		KruskalResult res = new Kruskal(edge).doit();
		
		res.sum += n * m;
		
		out.println(res.sum);
		visited = new boolean[k];
		dfs(0, -1, res);
		
		out.close();
	}
	
	/*
	int n, m, k, w;
	int res = 0;
	int[][] edge;
	ArrayList<Integer>[] usedNode;
	boolean[] ok;
	int cnt = 0;
	
	PriorityQueue<State> pq = new PriorityQueue<State>();
	
	class State implements Comparable<State> {
		int x, y;
		
		State(int x, int y) {
			this.x = x;
			this.y = y;
		}

		public int compareTo(State s) {
			int c1 = edge[y][x];
			int c2 = edge[s.y][s.x];
			if (c1 < c2) return -1;
			else if (c1 > c2) return 1;
			else return 0;
		}
	}
	
	boolean hasLoop(int start, int next, int before) {
		for (Integer node : usedNode[next]) {
			if (node == before) continue;
			if (node == start) return true;
			if (hasLoop(start, node, next))
				return true;
		}
		return false;
	}
	
	void prim() {
		int edgeNum = 0;
		while (!pq.isEmpty()) {
			State s = pq.poll();

			usedNode[s.x].add(s.y);
			usedNode[s.y].add(s.x);
			if (hasLoop(s.x, s.y, s.x)) {
				usedNode[s.x].remove(usedNode[s.x].size() - 1);
				usedNode[s.y].remove(usedNode[s.y].size() - 1);
			} else {
				if (edge[s.y][s.x] * w < n * m)
					res += edge[s.y][s.x] * w;
				else {
					res += n * m;
					edge[s.y][s.x] = edge[s.x][s.y] = -1;
				}
				if (++edgeNum == k - 1) break;
			}
		}
	}
	
	@SuppressWarnings("unchecked")
	public void run() {
		n = in.nextInt(); m = in.nextInt(); k = in.nextInt(); w = in.nextInt();
		
		char[][][] map = new char[k][n][];
		edge = new int[k][k];
		usedNode = new ArrayList[k];
		ok = new boolean[k];
		
		for (int i = 0; i < k; i++) {
			for (int y = 0; y < n; y++) {
				map[i][y] = in.next().toCharArray();
			}
		}
		
		for (int i = 0; i < k; i++) {
			usedNode[i] = new ArrayList<Integer>();
			for (int j = i + 1; j < k; j++) {
				for (int y = 0; y < n; y++) {
					for (int x = 0; x < m; x++) {
						if (map[i][y][x] != map[j][y][x]) {
							edge[i][j]++; 
						}
					}
				}
				edge[j][i] = edge[i][j];
				
				pq.add(new State(i, j));
			}
		}
		
		prim();
		out.println((res + n * m));
		out.println("1 0");
		
		ArrayList<Integer> preList = new ArrayList<Integer>();
		ArrayList<Integer> nextPreList = new ArrayList<Integer>();
		
		preList.add(0);
		Arrays.fill(ok, false);
		ok[0] = true;
		cnt = 1;
		
		while (!preList.isEmpty()) {
			for (Integer pre : preList) {
				for (Integer v : usedNode[pre]) {
					if (ok[v]) continue;
					ok[v] = true;
					cnt++;
					if (edge[v][pre] == -1)
						out.println((v+1) + " 0");
					else 
						out.println((v+1) + " " + (pre+1));
					nextPreList.add(v);
				}
			}
			preList.clear();
			for (Integer pre : nextPreList)
				preList.add(pre);
			nextPreList.clear();
		}
		
		out.close();
	}
	*/
	
	public static void main(String[] args) {
		new C().run();
	}

	public void mapDebug(int[][] a) {
		System.out.println("--------map display---------");

		for (int i = 0; i < a.length; i++) {
			for (int j = 0; j < a[i].length; j++) {
				System.out.printf("%3d ", a[i][j]);
			}
			System.out.println();
		}

		System.out.println("----------------------------");
		System.out.println();
	}
	
	public void debug(Object... obj) {
		System.out.println(Arrays.deepToString(obj));
	}

	class FastScanner {
		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;

		public FastScanner(InputStream stream) {
			this.stream = stream;
			//stream = new FileInputStream(new File("dec.in"));

		}

		int read() {
			if (numChars == -1)
				throw new InputMismatchException();
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = stream.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (numChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}

		boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		boolean isEndline(int c) {
			return c == '\n' || c == '\r' || c == -1;
		}

		int nextInt() {
			return Integer.parseInt(next());
		}

		long nextLong() {
			return Long.parseLong(next());
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}

		String next() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		String nextLine() {
			int c = read();
			while (isEndline(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isEndline(c));
			return res.toString();
		}
	}
}

