{"trustable":false,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"MD","content":"Во время запуска игры «Dungeons and Candies» требуется получить по сети от сервера описания $k$ уровней игры. Каждое описание — карта клетчатого прямоугольного поля $n × m$, в клетках которого расположены конфеты (в каждой клетке находится не более одной конфеты). Пустая клетка обозначается символом «.», если же в клетке находится конфета, то она кодируется буквой латинского алфавита. Уровень может содержать одинаковые конфеты, в таком случае буквы в соответствующих клетках карты будут одинаковы.\n \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/4c2ba2f7af3fc0248d3c64147867b39f?v\u003d1685642174\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e\n\u003c/center\u003e\nПри передачи по сети требуется минимизировать трафик — суммарный размер переданных данных. Уровни можно передавать в любом порядке. Существует два способа передать очередной уровень $A$:\n\nМожно передать уровень $A$ целиком. Этот способ требует передачи $n·m$ байтов по сети.\nМожно передать разницу между уровнем $A$ и каким-то ранее переданным уровнем $B$, если такой существует; эта операция требует передачи $d_{A,B}·w$ байтов, где $d_{A, B}$ обозначает количество клеток поля, которые отличаются в $A$ и $B$, а $w$ — константа. Обратите внимание, что при вычислении $d_{A, B}$ сравниваются соответствующие друг другу клетки уровней $A$ и $B$. При этом карты уровней нельзя преобразовывать, например, поворачивать или смещать относительно друг друга.\n\nВаша задача — найти способ передать все $k$ уровней, минимизировав трафик."}},{"title":"Input","value":{"format":"MD","content":"В первой строке записаны четыре целых числа $n, m, k, w$ $(1 ≤ n, m ≤ 10; 1 ≤ k, w ≤ 1000)$. Далее следует описание $k$ уровней. Каждый уровень описывается $n$ строками, в каждой из которых записано m символов. Каждый символ — это либо буква латинского алфавита, либо точка («.»). \n\nОбратите внимание, что регистр букв имеет значение."}},{"title":"Output","value":{"format":"MD","content":"В первой строке выведите искомое минимальное количество переданных байтов.\n\nДалее выведите $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$ должно быть равно номеру ранее переданного уровня, разницу по сравнению с которым нужно передать, т. е. вы передадите уровень $x_i$, передавая разницу между уровнями $x_i$ и $y_i$. Пары выводите в порядке передачи уровней. Уровни пронумерованы от $1$ до $k$ в порядке их описания во входных данных.\n\nЕсли существует несколько оптимальных решений, разрешается вывести любое."}},{"title":"Sample 1","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2 3 3 2\nA.A\n...\nA.a\n..C\nX.Y\n...\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e14\n1 0\n2 1\n3 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Sample 2","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1 1 4 1\nA\n.\nB\n.\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\n1 0\n2 0\n4 2\n3 0\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Sample 3","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1 3 5 2\nABA\nBBB\nBBA\nBAB\nABB\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e11\n1 0\n3 1\n2 3\n4 2\n5 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}