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:
- 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 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.
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
Solution:
#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <memory.h>
#include <cassert>
using namespace std;
const int inf = (int)1e9;
const int N = 1010;
char level[N][13][13];
int g[N][N];
int d[N], pr[N];
bool b[N];
int ans[N];
int main() {
int h, w, n, c;
scanf("%d %d %d %d", &h, &w, &n, &c);
for (int i = 1; i <= n; i++) {
for (int j = 0; j < h; j++) {
scanf("%s", level[i][j]);
}
}
for (int i = 1; i <= n; i++) {
g[i][i] = 0;
for (int j = i + 1; j <= n; j++) {
int cnt = 0;
for (int x = 0; x < h; x++) {
for (int y = 0; y < w; y++) {
cnt += (level[i][x][y] != level[j][x][y]);
}
}
g[i][j] = g[j][i] = c * cnt;
}
}
for (int i = 1; i <= n; i++) {
g[0][i] = g[i][0] = h * w;
}
g[0][0] = 0;
for (int i = 0; i <= n; i++) {
d[i] = inf;
b[i] = true;
pr[i] = -1;
}
d[0] = 0;
int res = 0;
for (int it = 0; it <= n; it++) {
int mn = inf, km = -1;
for (int i = 0; i <= n; i++) {
if (b[i] && d[i] < mn) {
mn = d[i];
km = i;
}
}
b[km] = false;
res += mn;
ans[it] = km;
for (int j = 0; j <= n; j++) {
if (b[j] && g[km][j] < d[j]) {
d[j] = g[km][j];
pr[j] = km;
}
}
}
printf("%d\n", res);
for (int i = 1; i <= n; i++) {
printf("%d %d\n", ans[i], pr[ans[i]]);
}
return 0;
}
