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
/*
 ID: govind.3, GhpS, govindpatel
 LANG: JAVA
 TASK: Main 
 */

import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class Main {

    /**
     * Min segment Tree takes the minimum number at the root
     */
    class MinSegmentTree {

        /**
         * root: Tree root, balance: input array, rl,rr:
         * rl=0,rr=inputArray.length-1 minTree:segment Tree
         */
        private void initMinTree(int root, int rl, int rr, int[] balance, int[] minTree) {
            if (rl == rr) {
                minTree[root] = balance[rl];
                return;
            }
            int rm = (rl + rr) / 2;
            initMinTree(root * 2 + 1, rl, rm, balance, minTree);
            initMinTree(root * 2 + 2, rm + 1, rr, balance, minTree);
            minTree[root] = Math.min(minTree[root * 2 + 1], minTree[root * 2 + 2]);
        }

        /**
         * minTree:segment tree root:0 rl:0,rr:inputarray.length-1
         * l=queryleft-1(If 1 based index),r = queryright(1-based)
         */
        private int getMin(int[] minTree, int root, int rl, int rr, int l, int r) {
            //l = query left-1, r = query right
            if (l > r) {
                return Integer.MAX_VALUE;
            }
            if (l == rl && r == rr) {
                return minTree[root];
            }
            int rm = (rl + rr) / 2;
            return Math.min(getMin(minTree, root * 2 + 1, rl, rm, l, Math.min(r, rm)),
                    getMin(minTree, root * 2 + 2, rm + 1, rr, Math.max(rm + 1, l), r));
        }
    }
    //dsu next operation
    int[] next;

    private int next(int i) {
        if (next[i] == i) {
            return i;
        }
        return next[i] = next(next[i]);
    }

    //segment tree...
    private void set(int[] t, int ind, int val) {
        ind += (t.length / 2);
        t[ind] = val;
        int curr = 0;
        while (ind > 1) {
            ind >>= 1;
            if (curr == 0) {
                t[ind] = t[ind * 2] | t[ind * 2 + 1];
            } else {
                t[ind] = t[ind * 2] ^ t[2 * ind + 1];
            }
            curr ^= 1;
        }
    }

    //Binary Index tree
    class FenwickTree {

        int[] ft;
        int N;

        FenwickTree(int n) {
            this.N = n;
            ft = new int[N];
        }

        private int lowbit(int x) {
            return x & (-x);
        }

        void update(int pos, int val) {
            while (pos < N) {
                ft[pos] += val;
                pos |= pos + 1;//0-index
            }
        }

        int sum(int pos) {
            int sum = 0;
            while (pos >= 0) {
                sum += ft[pos];
                pos = (pos & (pos + 1)) - 1;
            }
            return sum;
        }

        int rangeSum(int left, int right) {
            return sum(right) - sum(left - 1);
        }
    }

    /**
     * BINARY SEARCH IN FENWICK TREE: l=1, r=N(length), at=sumRequired,
     * letter=TreeIndex(if there are many ft), ft=arrays of FT
     */
    private int binarySearch(int l, int r, int at, int letter, FenwickTree[] ft) {
        while (r - l > 0) {
            int mid = (l + r) / 2;
            int sum = ft[letter].sum(mid);
            if (sum < at) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return l;
    }

    private int[] compress(int[] a) {
        int[] b = new int[a.length];
        for (int i = 0; i < a.length; i++) {
            b[i] = a[i];
        }
        Arrays.sort(b);
        int m = 0;
        for (int i = 0; i < b.length;) {
            int j = i;
            while (j < b.length && b[j] == b[i]) {
                j++;
            }
            b[m++] = b[i];
            i = j;
        }
        for (int i = 0; i < a.length; i++) {
            a[i] = Arrays.binarySearch(b, 0, m, a[i]);
        }
        return a;
    }

    class Dijkstra {

        class Edge implements Comparable<Edge> {

            int to;
            long weight;

            Edge(int t, long w) {
                to = t;
                weight = w;
            }

            public int compareTo(Edge other) {
                return (int) Math.signum(weight - other.weight);
            }
        }
        public static final long INF = (long) 1e17;
        private ArrayList<Edge> adj[];
        private int nodes;
        private long[] dist;
        private int[] prev;
        private boolean[] visited;

        public Dijkstra(int n) {
            nodes = n;
            adj = new ArrayList[nodes];
            dist = new long[nodes];
            prev = new int[nodes];
            visited = new boolean[nodes];
            for (int i = 0; i < nodes; i++) {
                adj[i] = new ArrayList<Edge>();
                dist[i] = INF;
                prev[i] = -1;
            }
        }

        public void add(int u, int v, long cost) {
            adj[u].add(new Edge(v, cost));
        }

        public void dist() {
            //src vertex = 0;
            dist[0] = 0;
            Queue<Edge> q = new PriorityQueue<Edge>();
            q.add(new Edge(0, 0));
            while (!q.isEmpty()) {
                Edge e = q.poll();
                int ind = e.to;
                if (visited[ind]) {
                    continue;
                }
                visited[ind] = true;

                for (Edge edge : adj[ind]) {
                    long newDistance = e.weight + edge.weight;
                    if (newDistance < dist[edge.to]) {
                        dist[edge.to] = newDistance;
                        prev[edge.to] = ind;
                        q.add(new Edge(edge.to, dist[edge.to]));
                    }
                }
            }
        }

        public ArrayList<Integer> getPrevList(int last) {
            ArrayList<Integer> al = new ArrayList<Integer>();
            while (last != -1) {
                al.add(last);
                last = prev[last];
            }
            return al;
        }

        public int[] getPrev() {
            return prev;
        }

        public long[] getDistance() {
            return dist;
        }

        public boolean[] getVisited() {
            return visited;
        }
    }

    class Edge implements Comparable<Edge> {

        int to;
        long dist;

        Edge(int t, long d) {
            to = t;
            dist = d;
        }

        public int compareTo(Edge other) {
            return Long.compare(dist, other.dist);
        }
    }

    private void solve() throws IOException {
        int height = nextInt();
        int width = nextInt();
        int N = nextInt();
        int cost = nextInt();
        int all = height * width;
        char[][] ch = new char[N + 1][all];
        ch[0] = new char[height * width];//add a dummy field...
        for (int i = 1; i <= N; i++) {
            String[] s = new String[height];
            for (int j = 0; j < height; j++) {
                s[j] = nextToken();
            }
            int ind = 0;
            for (int j = 0; j < height; j++) {
                for (int k = 0; k < width; k++) {
                    ch[i][ind] = s[j].charAt(k);
                    ind++;
                }
            }
        }

        int[] d = new int[N + 1];
        int[] from = new int[N + 1];
        boolean[] was = new boolean[N + 1];
        Arrays.fill(d, Integer.MAX_VALUE);
        d[0] = 0;
        int[] ansx = new int[N];
        int[] ansy = new int[N];
        int allCost = 0;
        int count = 0;

        while (true) {
            int best = -1;

            for (int i = 0; i <= N; i++) {//best ind to start with...
                if (was[i] || d[i] == Integer.MAX_VALUE) {
                    continue;
                }
                if (best < 0 || d[best] > d[i]) {
                    best = i;
                }
            }

            if (best == -1) {
                break;
            }

            char[] c1 = ch[best];
            was[best] = true;
            allCost += d[best];

            if (best > 0) {//not a dummy field...
                ansx[count] = best;
                ansy[count] = from[best];
                ++count;
            }

            for (int i = 0; i <= N; i++) {//compare with others..
                if (was[i]) {
                    continue;
                }
                char[] c2 = ch[i];
                int currCost = 0;
                int bestCost = all;
                for (int j = 0; j < all && currCost < bestCost; j++) {
                    if (c1[j] != c2[j]) {
                        currCost += cost;
                    }
                }
                bestCost = Math.min(bestCost, currCost);
                if (d[i] > bestCost) {//found min cost for ith field..
                    d[i] = bestCost;
                    from[i] = best;//update from...
                }
            }
        }

        out.println(allCost);
        for (int i = 0; i < count; i++) {
            out.println(ansx[i] + " " + ansy[i]);
        }
    }

    boolean isSorted(ArrayList<Integer> al) {
        int size = al.size();
        for (int i = 1; i < size - 2; i++) {
            if (al.get(i) > al.get(i + 1)) {
                return false;
            }
        }
        return true;
    }

    /**
     * SHUFFLE: shuffle the array 'a' of size 'N'
     */
    private void shuffle(int[] a, int N) {
        for (int i = 0; i < N; i++) {
            int r = i + (int) ((N - i) * Math.random());
            int t = a[i];
            a[i] = a[r];
            a[r] = t;
        }
    }

    /**
     * TEMPLATE-STUFF: main method, run method - ( fileIO and stdIO ) and
     * various methods for input like nextInt, nextLong, nextToken and
     * nextDouble with some declarations.
     */
    /**
     * For solution to the problem ... see the solve method
     */
    public static void main(String[] args) {
        new Main().run();
    }

    public void run() {
        try {
            in = new BufferedReader(new FileReader("D-large.in"));
            out = new PrintWriter(new BufferedWriter(new FileWriter("Main.out")));
            tok = null;
            solve();
            in.close();
            out.close();
            System.exit(0);
        } catch (IOException e) {//(FileNotFoundException e) {
            try {
                in = new BufferedReader(new InputStreamReader(System.in));
                out = new PrintWriter(new OutputStreamWriter(System.out));
                tok = null;
                solve();
                in.close();
                out.close();
                System.exit(0);
            } catch (IOException ex) {
                System.out.println(ex.getMessage());
                System.exit(0);
            }
        }
    }

    private String nextToken() throws IOException {
        while (tok == null || !tok.hasMoreTokens()) {
            tok = new StringTokenizer(in.readLine());
        }
        return tok.nextToken();
    }

    private int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

    private long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }

    private double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }
    BufferedReader in;
    StringTokenizer tok;
    PrintWriter out;
}
