CF436C.Dungeons and Candies

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.

在加载游戏《地牢与糖果》（Dungeons and Candies）时，你需要从服务器获取 k 个关卡的描述。每个描述是一张 n × m 的方格矩形地图。地图中某些格子包含糖果（每个格子至多含一颗糖果）。空格子在地图上用字符 . 表示；若某格子含有糖果，则用一个英文字母表示。一个关卡中可能包含相同的糖果，此时地图中对应格子的字母也相同。

在网络上传输信息时，你希望最小化网络流量——即传输数据的总大小。这些关卡可以按任意顺序传输。对于当前待传输的关卡 A，有两种传输方式：

1. 直接完整传输关卡 A：此时需通过网络传输 n·m 字节。
2. 传输关卡 A 相对于某个已传输过的关卡 B（若存在）的差异：该操作需传输 d__A, B·w 字节，其中 d__A, B 是关卡 A 与 B 在对应位置上格子内容不同的数量，w 是一个常数。注意，计算 d__A, B 时仅需逐格比较关卡 A 和 B 的对应格子；不允许对关卡地图进行任何变换（例如旋转或平移）。

你的任务是找出一种传输全部 k 个关卡的方式，使得总网络流量最小。

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.

第一行包含四个整数 $n$、$m$、$k$、$w$（$1 \leq n, m \leq 10$；$1 \leq k, w \leq 1000$）。随后是 $k$ 个关卡的描述。每个关卡由 $n$ 行组成，每行包含 $m$ 个字符。每个字符要么是英文字母，要么是一个英文句点（.）。请注意，字母的大小写是有区别的。

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.

第一行输出所需的最少传输字节数。

然后输出 $k$ 对整数 $x_1,\ y_1,\ x_2,\ y_2,\ \dots,\ x_k,\ y_k$，描述关卡的传输方案。每对 $x_i,\ y_i$ 表示关卡 $x_i$ 需通过方式 $y_i$ 进行传输。若 $y_i = 0$，表示该关卡必须使用第一种方式传输；否则 $y_i$ 必须等于某个先前已传输的关卡编号。这意味着你将通过传输关卡 $y_i$ 与关卡 $x_i$ 之间的差异来传输关卡 $x_i$。请按关卡传输顺序输出这些数对。关卡按输入中出现的顺序编号为 $1$ 至 $k$。

若存在多个最优解，输出任意一个即可。