题目描述

在加载游戏“地牢与糖果”时，你需要从服务器获取 $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$。

如果有多个最优解，可以输出其中任意一个。

样例

2 3 3 2
A.A
...
A.a
..C
X.Y
...

14
1 0
2 1
3 1

1 1 4 1
A
.
B
.

3
1 0
2 0
4 2
3 0

1 3 5 2
ABA
BBB
BBA
BAB
ABB

11
1 0
3 1
2 3
4 2
5 1