{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n div.illustration {\n float: right;\n padding-left: 20px;\n }\n div.illustration .illustration {\n width: 100%;\n border-radius: 4px;\n }\n pre {\n display: block;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n color: #333;\n word-break: break-all;\n word-wrap: break-word;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\n \u003cp\u003ePipe games are interesting and hard puzzle games. In these\n games, our mission is to connect the pipes to make the water\n flow in the pipeline from a source to a destination, without\n leaking out. Today we are playing a new generation of pipe\n game, the Ultimate Pipe Game.\u003c/p\u003e\n \u003cp\u003eIn this game, we have a grid of \u003cspan class\u003d\"tex2jax_process\"\u003e$m$\u003c/span\u003e rows and \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e columns. Cells on the grid are\n either empty or blocked. The cell at row \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e and column \u003cspan class\u003d\"tex2jax_process\"\u003e$j$\u003c/span\u003e is denoted as cell \u003cspan class\u003d\"tex2jax_process\"\u003e$(i, j)$\u003c/span\u003e. We only put pipes on empty\n cells and each cell can contain only one pipe. There are\n \u003cspan class\u003d\"tex2jax_process\"\u003e$3$\u003c/span\u003e kinds of pipes: curved\n pipes, horizontal pipes, and vertical pipes. Note that a curved\n pipe can be rotated as shown in the picture below, but we\n cannot rotate a horizontal pipe to make a vertical pipe or\n vice-versa.\u003c/p\u003e\n \u003ccenter\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/546dc545a6f9e5078131810d884f56a4?v\u003d1715427040\" alt\u003d\"\\includegraphics[width\u003d0.7\\textwidth ]{F1.png}\" style\u003d\"width:70.00%\"\u003e\n \u003c/center\u003e\n \u003cp\u003eBy putting pipes on empty cells, water from a cell can\n travel to its adjacent cell if and only if the pipes in two\n cells are connected by their heads.\u003c/p\u003e\n \u003cp\u003eOur mission in this Ultimate Pipe Game is to place pipes on\n the empty cells with following requirements:\u003c/p\u003e\n \u003cul class\u003d\"itemize\"\u003e\n \u003cli\u003e\n \u003cp\u003eWe need to put pipes on \u003cb class\u003d\"bfseries\"\u003eevery\u003c/b\u003e\n empty cell and each empty cell must contain exactly one\n pipe.\u003c/p\u003e\n \u003c/li\u003e\n \u003cli\u003e\n \u003cp\u003eWe have to make sure water in the pipeline will not leak\n out. Starting from any empty cell with a pipe, assuming\n that we have water flows out from that pipe in one of the\n two directions, water can travel through the pipeline to\n other cells without leaking out and return to the starting\n cell. In this case, we call it a \u003cb class\u003d\"bfseries\"\u003ecycle\n pipeline\u003c/b\u003e.\u003c/p\u003e\n \u003c/li\u003e\n \u003cli\u003e\n \u003cp\u003eWe can have multiple disjoint \u003cb class\u003d\"bfseries\"\u003ecycle\n pipelines\u003c/b\u003e.\u003c/p\u003e\n \u003c/li\u003e\n \u003cli\u003e\n \u003cp\u003ePutting a horizontal pipe and a vertical pipe at cell\n \u003cspan class\u003d\"tex2jax_process\"\u003e$(i, j)$\u003c/span\u003e cost\n \u003cspan class\u003d\"tex2jax_process\"\u003e$h_{i,j}$\u003c/span\u003e and\n \u003cspan class\u003d\"tex2jax_process\"\u003e$v_{i,j}$\u003c/span\u003e coins,\n respectively. Putting a curved pipe is free.\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ul\u003e\n \u003ccenter\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/e8107564f54efbf9d69a8c8d84d708c6?v\u003d1715427040\" alt\u003d\"\\includegraphics[width\u003d0.9\\textwidth ]{F2.jpg}\" style\u003d\"width:90.00%\"\u003e\n \u003c/center\u003e\n \u003cp\u003eYour task is to find a way, if one exists, to put pipes on\n empty cells to minimize the total cost (in terms of coins). You\n can assume that there are unlimited number of pipes.\u003c/p\u003e\n \u003ccenter\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/bdb1c64f76a89390386753aebce3a729?v\u003d1715427040\" alt\u003d\"\\includegraphics[width\u003d0.7\\textwidth ]{F3.png}\" style\u003d\"width:70.00%\"\u003e\n \u003c/center\u003e\n \u003ccenter\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/4ee1ffc87888e49c1a38c0859df7e374?v\u003d1715427040\" alt\u003d\"\\includegraphics[width\u003d0.7\\textwidth ]{F4.png}\" style\u003d\"width:70.00%\"\u003e\n \u003c/center\u003e\n \u003ch2\u003eInput\u003c/h2\u003e\n \u003cp\u003eThe input consists of several datasets. The first line of\n the input contains the number of datasets, which is a positive\n number and is not greater than \u003cspan class\u003d\"tex2jax_process\"\u003e$100$\u003c/span\u003e. The following lines describe\n the datasets.\u003c/p\u003e\n \u003cp\u003eEach dataset is described by the following lines:\u003c/p\u003e\n \u003cul class\u003d\"itemize\"\u003e\n \u003cli\u003e\n \u003cp\u003eFirst line contains two integers \u003cspan class\u003d\"tex2jax_process\"\u003e$m$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e \u003cspan class\u003d\"tex2jax_process\"\u003e$(2 \\le m, n \\le 20)$\u003c/span\u003e.\u003c/p\u003e\n \u003c/li\u003e\n \u003cli\u003e\n \u003cp\u003eThe next \u003cspan class\u003d\"tex2jax_process\"\u003e$m$\u003c/span\u003e lines\n describe the grid where each line contains \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e characters. The \u003cspan class\u003d\"tex2jax_process\"\u003e$j^\\textrm {th}$\u003c/span\u003e character at\n \u003cspan class\u003d\"tex2jax_process\"\u003e$i^\\textrm {th}$\u003c/span\u003e line\n denotes the state of cell \u003cspan class\u003d\"tex2jax_process\"\u003e$(i, j)$\u003c/span\u003e: “.” for an empty cell or\n # for a blocked cell.\u003c/p\u003e\n \u003c/li\u003e\n \u003cli\u003e\n \u003cp\u003eIn the next \u003cspan class\u003d\"tex2jax_process\"\u003e$m$\u003c/span\u003e\n lines, each line contains \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e integers denoting the cost of\n putting a horizontal pipe on a cell. The \u003cspan class\u003d\"tex2jax_process\"\u003e$j^\\textrm {th}$\u003c/span\u003e number on the\n \u003cspan class\u003d\"tex2jax_process\"\u003e$i^\\textrm {th}$\u003c/span\u003e line\n is an integer \u003cspan class\u003d\"tex2jax_process\"\u003e$h_{i,j}$\u003c/span\u003e \u003cspan class\u003d\"tex2jax_process\"\u003e$(0 \\le h_{i,j} \\le 100)$\u003c/span\u003e where\n \u003cspan class\u003d\"tex2jax_process\"\u003e$h_{i,j}$\u003c/span\u003e is\n \u003cspan class\u003d\"tex2jax_process\"\u003e$0$\u003c/span\u003e for a blocked\n cell.\u003c/p\u003e\n \u003c/li\u003e\n \u003cli\u003e\n \u003cp\u003eIn the last \u003cspan class\u003d\"tex2jax_process\"\u003e$m$\u003c/span\u003e\n lines, each line contains \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e integers denoting the cost of\n putting a vertical pipe on a cell. The \u003cspan class\u003d\"tex2jax_process\"\u003e$j^\\textrm {th}$\u003c/span\u003e number on the\n \u003cspan class\u003d\"tex2jax_process\"\u003e$i^\\textrm {th}$\u003c/span\u003e line\n is an integer \u003cspan class\u003d\"tex2jax_process\"\u003e$v_{i,j}$\u003c/span\u003e \u003cspan class\u003d\"tex2jax_process\"\u003e$(0 \\le v_{i,j} \\le 100)$\u003c/span\u003e where\n \u003cspan class\u003d\"tex2jax_process\"\u003e$v_{i,j}$\u003c/span\u003e is\n \u003cspan class\u003d\"tex2jax_process\"\u003e$0$\u003c/span\u003e for a blocked\n cell.\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ul\u003e\n \u003ch2\u003eOutput\u003c/h2\u003e\n \u003cp\u003eFor each dataset, output the result in the following\n format.\u003c/p\u003e\n \u003cul class\u003d\"itemize\"\u003e\n \u003cli\u003e\n \u003cp\u003eIf you can find a way to put pipes on empty cells to\n fulfill the requirements, output “YES \u003cspan class\u003d\"tex2jax_process\"\u003e$y$\u003c/span\u003e” where \u003cspan class\u003d\"tex2jax_process\"\u003e$y$\u003c/span\u003e is the minimum total number of\n coins we need to pay.\u003c/p\u003e\n \u003c/li\u003e\n \u003cli\u003e\n \u003cp\u003eOtherwise, output “NO”.\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ul\u003e\n \u003ch2\u003eSample 1\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\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\u003e3\n4 4\n##..\n##..\n..##\n..##\n0 0 1 2\n0 0 3 0\n1 2 0 0\n2 3 0 0\n0 0 1 2\n0 0 3 0\n1 2 0 0\n2 3 0 0\n3 4\n...#\n.#..\n....\n1 2 3 0\n4 0 1 2\n3 1 2 3\n3 2 1 0\n5 0 2 2\n3 1 2 3\n3 3\n...\n...\n...\n0 0 0\n0 0 0\n0 0 0\n1 1 1\n1 1 1\n1 1 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eYES 0\nYES 10\nNO\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}