Dungeons and Candies

2000ms

262144K

Description:

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.

$\text{[math]}$

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:

You can transmit the whole level A. Then you need to transmit n·m bytes via the network.
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₁, y₁, x₂, y₂, ..., 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.

Sample Input:

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

Sample Output:

Sample Input:

1 1 4 1
A
.
B
.

Sample Output:

Sample Input:

1 3 5 2
ABA
BBB
BBA
BAB
ABB

Sample Output:

Informação

Provedor Codeforces

Código CF436C