CF436C Dungeons and Candies

在加载游戏“地牢与糖果”时，你需要从服务器获取 $k$ 个关卡的描述。每个描述是一个 $n×m$ 的方格矩形地图。地图上的一些格子包含糖果（每个格子最多有一颗糖果）。空单元格用 `.` 表示，而有糖果的单元格则用英文字母表示。一个关卡中可能包含相同的糖果，这种情况下地图上对应单元格的字母也会相同。  通过网络传输信息时，你希望最小化流量——即传输数据的总大小。关卡可以按任意顺序传输。传输当前关卡 $A$ 有两种方式： 1. 完整传输整个关卡 $A$。这需要通过网络传输 $n\times m$ 字节。 2. 传输关卡 $A$ 与之前传输过的某个关卡 $B$ 的差异（如果存在）；这个操作需要传输 $d_{A,B}\times w$ 字节，其中 $d_{A,B}$ 是 $A$ 和 $B$ 地图上不同格子的数量，$w$ 是一个常数。注意，计算 $d_{A,B}$ 时只需要比较关卡 $A$ 和 $B$ 对应位置的格子。你不能对地图进行旋转或相对移动等变换。 你的任务是找到传输所有 $k$ 个关卡的方法，并使流量最小。

第一行包含四个整数 $n,m,k,w(1\le n,m\le10,1\le k,w\le1000)$。接下来是$k$个关卡的描述。每个关卡由 $n$ 行描述，每行包含 $m$ 个字符。每个字符是英文字母或点号 `.`。请注意字母的大小写是敏感的。

第一行输出需要传输的最小字节数。 然后输出 $k$ 对整数 $x_{1},y_{1},x_{2},y_{2},...,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$。 如果有多个最优解，可以输出其中任意一个。