对于这种贡献和整体数量相关的问题，确实可以考虑和最小生成树挂上勾……
总体来说还是有点怪的，考虑转化为图论模型，物品两两之间建边，权值为相互转移的代价，再新建一个节点，每个点向其连边，权值为其直接代价，因为第一个必须要直接转移，所以跑一遍 MST 就行了。
总结一下 MST 的一些性质，贡献没有方向，对于顺序没有强的限制
#define tup tuple<int,int,int>
#include <numeric>
vector<tup> g;
char c[1010][11][11];
int n,m,k,w;
int f[1010],op[1010];
vector<int>ng[1010];
int cmp(int x,int y){
int cnt=0;
fp(i,1,n)fp(j,1,m) if(c[x][i][j]!=c[y][i][j]) ++cnt;
return cnt;
}
int acc(int x){
if(f[x]^x) return f[x]=acc(f[x]);
return x;
}
void dfs(int now,int f){
if(now!=k+1){
cout << now <<' ';
if(f==k+1) cout << 0 << endl;
else cout << f << endl;
}
for(int x:ng[now])
if(x^f) dfs(x,now);
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
n=rd(),m=rd(),k=rd(),w=rd();
fp(d,1,k)
fp(i,1,n)
fp(j,1,m){
c[d][i][j]=getchar();
while(isspace(c[d][i][j])) c[d][i][j]=getchar();
}
fp(d1,1,k)
fp(d2,d1,k)
g.emplace_back(d1,d2,w*cmp(d1,d2));
fp(i,1,k) g.emplace_back(i,k+1,n*m);
sort(g.begin(),g.end(),[](tup x,tup y){
return get<2>(x)<get<2>(y);
});
iota(f+1,f+k+2,1);
int ans=0;
for(auto [u,v,w]:g){
if(acc(u)==acc(v)) continue ;
ng[u].emplace_back(v),
ng[v].emplace_back(u);
ans+=w;
f[acc(u)]=acc(v);
}cout << ans << endl;
dfs(k+1,0);
return 0;
}