| Zepto Code Rush 2014 |
|---|
| Закончено |
Во время запуска игры «Dungeons and Candies» требуется получить по сети от сервера описания k уровней игры. Каждое описание — карта клетчатого прямоугольного поля n × m, в клетках которого расположены конфеты (в каждой клетке находится не более одной конфеты). Пустая клетка обозначается символом «.», если же в клетке находится конфета, то она кодируется буквой латинского алфавита. Уровень может содержать одинаковые конфеты, в таком случае буквы в соответствующих клетках карты будут одинаковы.
При передачи по сети требуется минимизировать трафик — суммарный размер переданных данных. Уровни можно передавать в любом порядке. Существует два способа передать очередной уровень A:
- Можно передать уровень A целиком. Этот способ требует передачи n·m байтов по сети.
- Можно передать разницу между уровнем A и каким-то ранее переданным уровнем B, если такой существует; эта операция требует передачи dA, B·w байтов, где dA, B обозначает количество клеток поля, которые отличаются в A и B, а w — константа. Обратите внимание, что при вычислении dA, B сравниваются соответствующие друг другу клетки уровней A и B. При этом карты уровней нельзя преобразовывать, например, поворачивать или смещать относительно друг друга.
Ваша задача — найти способ передать все k уровней, минимизировав трафик.
В первой строке записаны четыре целых числа n, m, k, w (1 ≤ n, m ≤ 10; 1 ≤ k, w ≤ 1000). Далее следует описание k уровней. Каждый уровень описывается n строками, в каждой из которых записано m символов. Каждый символ — это либо буква латинского алфавита, либо точка («.»). Обратите внимание, что регистр букв имеет значение.
В первой строке выведите искомое минимальное количество переданных байтов.
Далее выведите k пар целых чисел x1, y1, x2, y2, ..., xk, yk, описывающих способ передачи уровней. Пара xi, yi обозначает, что уровень xi нужно передавать способом yi. Если yi равно 0, значит, уровень нужно передавать первым способом, иначе yi должно быть равно номеру ранее переданного уровня, разницу по сравнению с которым нужно передать, т. е. вы передадите уровень xi, передавая разницу между уровнями xi и yi. Пары выводите в порядке передачи уровней. Уровни пронумерованы от 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
