#include <iostream>
#define fr(i,n) for(int i=1; i<=n; i++)
#define mp make_pair
#define MXN 1010
using namespace std;
int prev_min_ind[MXN], mincost[MXN], used[MXN];
int pr,tmincost,n,m,k,w;
pair<int,int > ans[MXN];
char lvl[MXN][15][15];
int main() {
cin>>n>>m>>k>>w;
fr(i,k) fr(j,n) cin>>lvl[i][j];
fr(i,k) mincost[i]=n*m, prev_min_ind[i]=0;
//1 is considered exclusively so i'm assuming prev sent was 1, note that
//this val wouldn't affect answer, you could send any level for first time so
//you could pr any val as far as pr<=k and print this chosen val exclusively
pr=1;
//i need atmost k-1 iterations as i have already chosen 1 vertex but still i need to choose k-1 nodes
//since in each iteration i'll choose at least(exactly) one node so max iterations = k - 1
//this is a very good implementation of prim's algo.
fr(i,k-1){
used[pr] = 1;
int cmincost = 10000, fminind = 0;
//search over all vertices which one gives min cost for sending after pr vertex if this is not used already
fr(x,k) if(!used[x]){
int cst=0;
//find cost of lvl x sending after level pr(if it will be sent in future after 1)
fr(y,n) for(int c=0; c<m; ++c) if(lvl[pr][y][c] != lvl[x][y][c]) cst += w;
//if this cost is less than any other cost, update values
if(mincost[x]>cst){ mincost[x] = cst; prev_min_ind[x]=pr; }
/**
*
* if choosing this x vertex gives me the lowest cost update current min out of all
* note that we are updating prev_min_ind array bcoz this min value might have come from some
* prev iteration of i when it was min in that iteration but in this iteration it became min
* so if this is the case prev_min_ind already have proper value, for second case it must have been
* modified in upper if block
*/
if(mincost[x]<cmincost){ cmincost=mincost[x]; fminind=x; }
}
tmincost += cmincost;
pr = fminind;
ans[i] = mp(pr, prev_min_ind[pr]);
}
cout<<tmincost+m*n<<endl;
printf("1 0\n");
fr(i,k-1) printf("%d %d\n",ans[i].first,ans[i].second);
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojZGVmaW5lIGZyKGksbikgZm9yKGludCBpPTE7IGk8PW47IGkrKykKI2RlZmluZSBtcCBtYWtlX3BhaXIKI2RlZmluZSBNWE4gMTAxMAoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmludCBwcmV2X21pbl9pbmRbTVhOXSwgbWluY29zdFtNWE5dLCB1c2VkW01YTl07CmludCBwcix0bWluY29zdCxuLG0sayx3OwpwYWlyPGludCxpbnQgPiBhbnNbTVhOXTsKY2hhciBsdmxbTVhOXVsxNV1bMTVdOwoKaW50IG1haW4oKSB7CiAgICBjaW4+Pm4+Pm0+Pms+Pnc7CiAgICAKICAgIGZyKGksaykgZnIoaixuKSBjaW4+Pmx2bFtpXVtqXTsgCiAgICAKICAgIGZyKGksaykgbWluY29zdFtpXT1uKm0sIHByZXZfbWluX2luZFtpXT0wOwogICAgLy8xIGlzIGNvbnNpZGVyZWQgZXhjbHVzaXZlbHkgc28gaSdtIGFzc3VtaW5nIHByZXYgc2VudCB3YXMgMSwgbm90ZSB0aGF0CiAgICAvL3RoaXMgdmFsIHdvdWxkbid0IGFmZmVjdCBhbnN3ZXIsIHlvdSBjb3VsZCBzZW5kIGFueSBsZXZlbCBmb3IgZmlyc3QgdGltZSBzbyAKICAgIC8veW91IGNvdWxkIHByIGFueSB2YWwgYXMgZmFyIGFzIHByPD1rIGFuZCBwcmludCB0aGlzIGNob3NlbiB2YWwgZXhjbHVzaXZlbHkgCiAgICBwcj0xOwogICAgLy9pIG5lZWQgYXRtb3N0IGstMSBpdGVyYXRpb25zIGFzIGkgaGF2ZSBhbHJlYWR5IGNob3NlbiAxIHZlcnRleCBidXQgc3RpbGwgaSBuZWVkIHRvIGNob29zZSBrLTEgbm9kZXMKICAgIC8vc2luY2UgaW4gZWFjaCBpdGVyYXRpb24gaSdsbCBjaG9vc2UgYXQgbGVhc3QoZXhhY3RseSkgb25lIG5vZGUgc28gbWF4IGl0ZXJhdGlvbnMgPSBrIC0gMQogICAgLy90aGlzIGlzIGEgdmVyeSBnb29kIGltcGxlbWVudGF0aW9uIG9mIHByaW0ncyBhbGdvLgogICAgZnIoaSxrLTEpewogICAgICAgIHVzZWRbcHJdID0gMTsKICAgICAgICBpbnQgY21pbmNvc3QgPSAxMDAwMCwgZm1pbmluZCA9IDA7CiAgICAgICAgLy9zZWFyY2ggb3ZlciBhbGwgdmVydGljZXMgd2hpY2ggb25lIGdpdmVzIG1pbiBjb3N0IGZvciBzZW5kaW5nIGFmdGVyIHByIHZlcnRleCBpZiB0aGlzIGlzIG5vdCB1c2VkIGFscmVhZHkKICAgICAgICBmcih4LGspIGlmKCF1c2VkW3hdKXsKICAgICAgICAgICAgaW50IGNzdD0wOwogICAgICAgICAgICAvL2ZpbmQgY29zdCBvZiBsdmwgeCBzZW5kaW5nIGFmdGVyIGxldmVsIHByKGlmIGl0IHdpbGwgYmUgc2VudCBpbiBmdXR1cmUgYWZ0ZXIgMSkKICAgICAgICAgICAgZnIoeSxuKSBmb3IoaW50IGM9MDsgYzxtOyArK2MpIGlmKGx2bFtwcl1beV1bY10gIT0gbHZsW3hdW3ldW2NdKSBjc3QgKz0gdzsKICAgICAgICAgICAgLy9pZiB0aGlzIGNvc3QgaXMgbGVzcyB0aGFuIGFueSBvdGhlciBjb3N0LCB1cGRhdGUgdmFsdWVzCiAgICAgICAgICAgIGlmKG1pbmNvc3RbeF0+Y3N0KXsgbWluY29zdFt4XSA9IGNzdDsgcHJldl9taW5faW5kW3hdPXByOyB9CiAgICAgICAgICAgIC8qKgogICAgICAgICAgICAgKiAKICAgICAgICAgICAgICogIGlmIGNob29zaW5nIHRoaXMgeCB2ZXJ0ZXggZ2l2ZXMgbWUgdGhlIGxvd2VzdCBjb3N0IHVwZGF0ZSBjdXJyZW50IG1pbiBvdXQgb2YgYWxsIAogICAgICAgICAgICAgKiAgbm90ZSB0aGF0IHdlIGFyZSB1cGRhdGluZyBwcmV2X21pbl9pbmQgYXJyYXkgYmNveiB0aGlzIG1pbiB2YWx1ZSBtaWdodCBoYXZlIGNvbWUgZnJvbSBzb21lCiAgICAgICAgICAgICAqICBwcmV2IGl0ZXJhdGlvbiBvZiBpIHdoZW4gaXQgd2FzIG1pbiBpbiB0aGF0IGl0ZXJhdGlvbiBidXQgaW4gdGhpcyBpdGVyYXRpb24gaXQgYmVjYW1lIG1pbgogICAgICAgICAgICAgKiAgc28gaWYgdGhpcyBpcyB0aGUgY2FzZSBwcmV2X21pbl9pbmQgYWxyZWFkeSBoYXZlIHByb3BlciB2YWx1ZSwgZm9yIHNlY29uZCBjYXNlIGl0IG11c3QgaGF2ZSBiZWVuCiAgICAgICAgICAgICAqICBtb2RpZmllZCBpbiB1cHBlciBpZiBibG9jawogICAgICAgICAgICAgKi8KICAgICAgICAgICAgaWYobWluY29zdFt4XTxjbWluY29zdCl7IGNtaW5jb3N0PW1pbmNvc3RbeF07IGZtaW5pbmQ9eDsgfQogICAgICAgIH0KICAgICAgICB0bWluY29zdCArPSBjbWluY29zdDsKICAgICAgICBwciA9IGZtaW5pbmQ7CiAgICAgICAgYW5zW2ldID0gbXAocHIsIHByZXZfbWluX2luZFtwcl0pOwogICAgfQogICAgY291dDw8dG1pbmNvc3QrbSpuPDxlbmRsOwogICAgcHJpbnRmKCIxIDBcbiIpOwogICAgZnIoaSxrLTEpIHByaW50ZigiJWQgJWRcbiIsYW5zW2ldLmZpcnN0LGFuc1tpXS5zZWNvbmQpOwp9Cg==