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.util.List;
import java.io.IOException;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.InputMismatchException;
import java.util.ArrayList;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.AbstractCollection;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskC solver = new TaskC();
        solver.solve(1, in, out);
        out.close();
    }
}

class TaskC {
    private int countDif(char levels[][][],int i,int j,int n,int m) {
        int count =  0;
        for(int x = 0;x<n;x++) {
           for(int y = 0;y<m;y++) {
               if(levels[i][x][y] != levels[j][x][y])
                   ++count;
           }
        }
        return count;
    }

    public void solve(int testNumber, InputReader in, PrintWriter out) {
        int n = in.nextInt();
        int m = in.nextInt();
        int k = in.nextInt();
        int w= in.nextInt();
        char levels[][][] = new char[k][n][m];
        for(int i=0;i<k;i++) {
            for(int j=0;j<n;j++) {
                String lstr = in.nextToken();
                for(int p = 0;p<lstr.length();p++) {
                    levels[i][j][p] = lstr.charAt(p);
                }
            }
        }
        int [][] difA = new int[k][k];
        SparseGraph g = new SparseGraph(k,k*k*2);
        for(int i=0; i<k;i++) {
            for(int j = 0;j<k;j++) {
                if(i==j)
                    continue;
                int dif =  countDif(levels, i, j, n, m)*w;
                difA[i][j] = dif;
                g.addEdge(i,j,Math.min(dif,m*n));
                g.addEdge(j,i,Math.min(dif,m*n));
            }
        }

        for(int i=1;i<n;i++) {
            g.addEdge(0,i,n*m);
            g.addEdge(i, 0, n * m);

        }

        SparseGraph mst = (SparseGraph) PrimsAlgorithms.getMstUsingHeap(g);

        ArrayList<Pair<Integer,Integer>> found= new ArrayList<Pair<Integer,Integer>>();
       // found.add(new Pair<Integer, Integer>(1,0));
        Integer totalW = 0;

        // add
        dfs(mst,0,-1,n*m,n,m,found,totalW);
        out.println(W);
        for(int i=0;i<found.size();i++) {
            out.println(found.get(i).first + " "  + found.get(i).second);
        }
    }
    public static int W = 0;
    private void dfs(SparseGraph mst, int v, int parent,int edge,int n,int m,ArrayList<Pair<Integer, Integer>> found,Integer totalW)
    {

       W += edge;
       if(parent == -1 || edge == n*m) {

           found.add(new Pair<Integer, Integer>(v+1,0));
       } else {
           found.add(new Pair<Integer, Integer>(v+1,parent+1));
       }

       int h = mst.Head[v];
       while(h!=-1) {
           dfs(mst,mst.To[h],v,Math.min(mst.Weight[h],n*m),n,m,found,totalW);
           h = mst.Next[h];
       }
    }
}

class InputReader {

    private InputStream stream;
    int curCharIndex = 0;
    int charsInBuf = 0;
     byte buf[] = new byte[16*1024];

    public InputReader(InputStream stream) {
        this.stream = stream;
    }


    public int readChar() {

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


    public int nextInt() {

        int c;
        do {
            c = readChar();
        }while(isWhitespace(c));

        int sign = 1;
        if (c == '-') {
            c = readChar();
            sign = -1;

        }
        int res = 0;
        do {
            res *= 10;
            res += c - '0';
            c = readChar();
        } while (!isWhitespace(c) && c!=-1);
        return sign * res;
    }


    public String nextToken() {
        int c;
        do {
            c = readChar();
        }while(isWhitespace(c));

        StringBuilder res = new StringBuilder();
        do {
            res.appendCodePoint(c);
            c = readChar();
        } while (!isWhitespace(c) && c!=-1);
        return res.toString();
    }

    /*
    * For the purpose of compatibilty with Chelper Chrome extension
     */


    private boolean isWhitespace(int c) {
        return  c==' ' || c=='\n'|| c=='\r' || c=='\t';
    }
}

class SparseGraph extends   Graph
{
    public int []From;
    public int []To;
    public int Head[];
    public int Next[];

    public int Weight[];
    int edgeCapacity;



    public SparseGraph(int vertexCount,int edgeCapacity)
    {
        From=new int[edgeCapacity];
        To=new int[edgeCapacity];
        Head=new int[vertexCount];
        Next=new int[edgeCapacity];
        Arrays.fill(Next,-1);
        Arrays.fill(Head,-1);
        this.edgeCapacity=edgeCapacity;

        this.vertexCount=vertexCount;
        edgeCount=0;
    }



    public void addEdge(int from, int to) {
        From[edgeCount]=from;
        To[edgeCount]=to;
        Next[edgeCount]=Head[from];
        Head[from]=edgeCount;
        ++edgeCount;

    }


    public void addEdge(int from, int to, int weight)
    {
        if(Weight==null)  {
            Weight=new int[edgeCapacity];
        }
        addEdge(from,to);
        Weight[edgeCount-1]=weight;
    }



    public List<Edge> getIncidentEdges(int vertexId)
    {
       ArrayList<Edge> list=new ArrayList<Edge>();
       int p=Head[vertexId];
       while(p!=-1) {
           Edge e=new Edge(To[p]);
           if(Weight!=null)  {
               e.weight = Weight[p];
           }
           list.add(e);
           p=Next[p];
       }
        return list;
    }


}

class PrimsAlgorithms
{
   /* returns a tree which is an MST of given graph G*/
   public static Graph getMstUsingHeap(Graph g)
   {

       Graph mst=new SparseGraph(g.getVertexCount(),g.getEdgeCount());
       int n = g.edgeCount;
       if(n == 0)
           return mst;
       boolean[] used = new boolean[n];
       int[] priority = new int[n];
       int[] prev=new int[g.getVertexCount()];
       Arrays.fill(priority, Integer.MAX_VALUE);
       Arrays.fill(prev,-1);
       priority[0] = 0;
       PriorityQueue<VertexInQueue> q = new PriorityQueue<VertexInQueue>();
       q.add(new VertexInQueue(0,0));
       while (!q.isEmpty()) {
           VertexInQueue v = q.poll();
           int u = (int) v.vertexId;
           if (used[u])
               continue;
           if(prev[u]!=-1)mst.addEdge(prev[u],u,v.minWeight);
           used[u] = true;
           for (Edge e : g.getIncidentEdges(u)) {
               int nextV = e.to;
               if (!used[nextV] && priority[nextV] > e.weight) {
                   priority[nextV] = e.weight;
                   prev[nextV]=u;
                   q.add(new VertexInQueue(nextV,priority[nextV]));
               }
           }
       }
       return mst;
   }


}

abstract class Graph
{
    public int vertexCount;
    public int edgeCount;
    public int getVertexCount()
    {
        return vertexCount;
    }

    abstract public void addEdge(int from,int to, int weight);


    public int getEdgeCount() {
        return edgeCount;
    }
    public abstract List<Edge> getIncidentEdges(int vertexId);
}

class Pair<FIRST, SECOND> implements Comparable<Pair<FIRST, SECOND>> {

    public final FIRST first;
    public final SECOND second;

    public Pair(FIRST first, SECOND second) {
        this.first = first;
        this.second = second;
    }

    public int compareTo(Pair<FIRST, SECOND> o) {
        int cmp = compare(first, o.first);
        return cmp == 0 ? compare(second, o.second) : cmp;
    }

    private static int compare(Object o1, Object o2) {
        return o1 == null ? o2 == null ? 0 : -1 : o2 == null ? +1
                : ((Comparable) o1).compareTo(o2);
    }

    public int hashCode() {
        return 31 * hashcode(first) + hashcode(second);
    }

    private static int hashcode(Object o) {
        return o == null ? 0 : o.hashCode();
    }

    public boolean equals(Object obj) {
        if (!(obj instanceof Pair))
            return false;
        if (this == obj)
            return true;
        return equal(first, ((Pair) obj).first)
                && equal(second, ((Pair) obj).second);
    }
    private boolean equal(Object o1, Object o2) {
        return o1 == null ? o2 == null : (o1 == o2 || o1.equals(o2));
    }

}

class Edge implements Comparable<Edge>
{
   int from;
   public int to;
   public int weight;

    public  Edge(int to)
    {
        //this.from=from;
        this.to=to;
    }
    public Edge(int to,int weight)
    {
       this(to);
       this.weight=weight;
    }
    public Edge(int from,int to,int weight)
    {
        this(to);
        this.from=from;
        this.weight=weight;
    }
    public int compareTo(Edge edge)
    {
        if(this.weight< edge.weight)
        {
            return -1;
        }
        else if(this.weight==edge.weight && this.to==edge.to && this.from==edge.from) {
            return 0;
        }
        else return 1;
    }


}

class VertexInQueue implements Comparable<VertexInQueue>
{
    int vertexId;
    int minWeight;
    public VertexInQueue(int vertexId, int minWeight)
    {
        this.vertexId=vertexId;
        this.minWeight=minWeight;
    }
    public int compareTo(VertexInQueue myVertex)
    {
        if(this.minWeight==myVertex.minWeight)
        {
            return 0;
        }
        else if(this.minWeight <myVertex.minWeight)
        {
            return -1;
        }
        return 1;
    }
}
