#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAXN=1e5+10;
struct Edge{
    int from,to,val;
};
vector<Edge> edges[MAXN];
void add(int from,int to,int val){
    Edge e={from,to,val};
    edges[from].push_back(e);
}
int dis[MAXN],vis[MAXN],cnt,ans,fa[MAXN];
int n,m,k,w;  
string s[1010][15];
priority_queue<pair<int,int>,std::vector<pair<int,int>>,std::greater<>> q;
int cal(int u,int v)
{
    int diff=0;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            if(s[u][i][j]!=s[v][i][j])  diff+=w;
        }
    }
    return diff;
}
std::vector<pair<int,int>> v;
void prim()
{
    memset(dis,0x3f,sizeof(dis));
    dis[1]=n*m;
    q.push({dis[1],1});
    while(!q.empty())
    {
        if(cnt>=k)  break;
        int d=q.top().first;
        int now=q.top().second;
        q.pop();
        if(vis[now])    continue;
        vis[now]=true;
        cnt++;
        ans+=d;
        if(d==n*m)
        {
            v.push_back({now,0});
        }
        else
        {
            v.push_back({now,fa[now]});
        }
        for (int i = 1; i <= k; ++i)
        {
            if(vis[i])  continue;
            int val=cal(i,now);
            if(val<dis[i])
            {
                dis[i]=val;
                fa[i]=now;
                q.push({dis[i],i});
            }
        }
    }
}
int main(){
  
    cin>>n>>m>>k>>w;
    for (int i = 1; i <= k; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            cin>>s[i][j];
        }
        fa[i]=i;
    }
    prim();
    cout<<ans<<"\n";
    for (int i = 0; i < k; ++i)
    {
        cout<<v[i].first<<" "<<v[i].second<<"\n";
    }
}

WA9了，这个是边跑prim时算边