{"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\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"MD","content":"爱丽丝正在玩一个流行的电脑角色扮演游戏“网格幻想”。这个游戏中的世界地图是一个有N列和M行的矩形。地图上的每个单元可以是城镇、荒野或山脉。此外,任何与城镇相邻的非山区单元都是荒野,任何与荒野相邻的非山区单元都是城镇。玩家可以在边界相邻的单元之间移动,但不能进入山区单元。从荒野搬到城镇要花A块金子,从城镇搬到荒野要花B块金子。\n\n起初,爱丽丝在地图的左上角,那是一个城镇。爱丽丝想移动到地图的右下角。帮爱丽丝找到她需要的最低数量的金子。"}},{"title":"Input","value":{"format":"MD","content":"输入的第一行包含两个整数n和m(1≤n,m≤500)-地图的宽度和高度。第二行包含两个整数A和B(0≤A,B≤1000)-进入城镇的成本和进入荒野的成本。\n接下来的m行每行包含一个n个字符的字符串。第j个字符串中的第i个字符包含“.”(相应的单元格可以被爱丽丝占用)和“#”(如果它是山区单元格)。"}},{"title":"Output","value":{"format":"MD","content":"输出应该包含一个整数-移动到右下角单元格所需的最小黄金量。如果不可能,请打印“不可能”。"}},{"title":"Examples","value":{"format":"MD","content":"\n Input\n \u003c/div\u003e\n \u003cpre\u003e5 3\u003cbr\u003e1 2\u003cbr\u003e.#...\u003cbr\u003e.#.#.\u003cbr\u003e...#.\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"output\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e\n \u003cpre\u003e15\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"input\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e\n \u003cpre\u003e3 3\u003cbr\u003e4 5\u003cbr\u003e..#\u003cbr\u003e.#.\u003cbr\u003e#..\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"output\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e\n \u003cpre\u003eIMPOSSIBLE\u003c/pre\u003e\n \u003c/div\u003e\n\u003c/div\u003e"}}]}