{"trustable":true,"prependHtml":"\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 async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003e″You are too young to be burdened with all my cares,″ the father told her, ″but you are also a Stark of Winterfell. You know our words.″\u003cbr\u003e″Winter is coming,″ Arya whispered, thinking of Nymeria. She hugged her knees against her chest, suddenly afraid.\u003cbr\u003e″Remember the sigil of our House, Arya. Let me tell you something about it. When the snows fall and the white winds blow, the lone Wolf dies, but the pack survives. Summer is the time for squabbles. In winter, we must protect one another, keep each other warm, share our strengths. So if you must hate, Arya, hate those who would truly do us harm. Sansa... Sansa is your sister. You may be as different as the sun and the moon, but the same blood flows through both your hearts. You need her, as she needs you... and I need both of you, gods help me. Gods commanded us to build a long wall, which is regardless of the thickness, to defend the attack from the Lannister. Now we should carry out the wall.″ Ned Stark sounded so tired that it made Arya sad.\u003cbr\u003e″I do not mean to frighten you, but neither will I lie to you. We have come to a dark dangerous place, child. We have enemies who mean us ill in the King\u0027s Landing. We\u0027ll point the swords to the Lannister, rather than fight a war among ourselves. Our construction crew will build a wall which connect the north border and south border, separate the mainland into exact two parts. All our Wolf\u0027s cities should lie on the left part, while All Lannister\u0027s cities lie on the right part. Precisely, the wall can\u0027t pass through a grid more than once, and should run parallel or vertically to the four borders. With winter soon upon us, that is a different matter that we should minimize the time cost.″\u003cbr\u003e″How much time do we have, roughly?″ Arya take out the draft and has been ready to calculate.\u003cbr\u003e″Winter is coming.″ Her father frowned.\u003cbr\u003e\u003ccenter\u003e\u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/0817b5a8b1697f0b6ecab983fdec4cca?v\u003d1725093416\"\u003e\u003c/center\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"There are multiple cases. The first line of each case contains two integers, N, M (1 ≤ N ≤ 20, 1 ≤ M ≤ 10), indicating the width and length of the mainland\u0027s layout.\u003cbr\u003eIn the map, the character is \u0027W\u0027 indicated the Wolf\u0027s city, \u0027L\u0027 indicated the Lannister\u0027s city, \u0027#\u0027 means a grid where forbade any construction, and a number in \u00270\u0027-\u00279\u0027 indicated the time cost to build a wall on this grid."}},{"title":"Output","value":{"format":"HTML","content":"For each case, output one integer, the minimum time cost to build a valid wall, or -1 if we can\u0027t work out an approach."}},{"title":"Sample","value":{"format":"HTML","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\u003e6 8\r\n88W888L8\r\n888#W888\r\n888888L8\r\n8W88L#88\r\n8888888L\r\n88888W88\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e88\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}