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.

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 $*d*_{*A*, *B*}·*w*$ bytes, where $*d*_{*A*, *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 $*d*_{*A*, *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 $*x*_{1}, *y*_{1}, *x*_{2}, *y*_{2}, ..., *x*_{*k*}, *y*_{*k*}$, describing the way to transfer levels. Pair $*x*_{*i*}$, $*y*_{*i*}$ means that level $*x*_{*i*}$ needs to be transferred by way $*y*_{*i*}$. If $*y*_{*i*}$ equals 0, that means that the level must be transferred using the first way, otherwise $*y*_{*i*}$ must be equal to the number of a previously transferred level. It means that you will transfer the difference between levels $*y*_{*i*}$ and $*x*_{*i*}$ to transfer level $*x*_{*i*}$. 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.