{"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据女神之书记载:在创世之后,残忍的神明摩洛克背叛了造物主马杜克的权威。摩洛克偷走了众神中最强大的神器——恩德尔护身符,并将其藏匿在地狱深渊的黑暗洞穴中,如今他就潜伏在那里,等待时机。\u003cbr\u003e\u003cbr\u003e你的女神希望拥有这个护身符,并借此获得应有的统治其他神明的权力。\u003cbr\u003e\u003cbr\u003e你,一名新近训练有素的漫游者,从出生起就被宣告为女神的工具。你注定要为你的女神夺回护身符,或者在尝试中死去。你的命运之时已至。为了我们所有人的利益:与女神一同勇敢前行吧!\u003cbr\u003e\u003cbr\u003e如果你玩过电脑游戏《地下城探险》,你一定对上述引用很熟悉。如果你从未听说过,不用担心。你很快就会了解它(并且爱上它)。\u003cbr\u003e\u003cbr\u003e在这个问题中,你,冒险者,身处危险的地牢。你得知地牢即将坍塌。你必须在规定时间内找到出口楼梯。然而,你不想空手离开地牢。地牢中有许多稀有宝石。在离开之前尽量收集一些。一些宝石价格较低,一些价格较高。因此,你将尽力最大化你的收藏,更重要的是,及时离开地牢。\u003cbr\u003e\u003c/div\u003e"}},{"title":"输入","value":{"format":"HTML","content":"标准输入包含多个测试用例。输入的第一行是一个整数 T(1 ≤ T ≤ 10),表示测试用例的数量。接下来是 T 个测试用例,每个测试用例之间有一个空行。\u003cbr\u003e\u003cbr\u003e每个测试用例的第一行包含四个整数 W(1 ≤ W ≤ 50)、H(1 ≤ H ≤ 50)、L(1 ≤ L ≤ 1,000,000)和 M(1 ≤ M ≤ 10)。地牢是一个宽度为 W 个方块、高度为 H 个方块的矩形区域。L 表示时间限制,你需要在这段时间内到达出口。你可以在每个时间单位内向上、向下、向左、向右移动到相邻的方块,只要目标方块在地牢内且不是墙壁。游戏开始时时间为 1。M 表示地牢中的宝石数量。冒险者到达该方块时将收集宝石,这不会额外消耗时间。\u003cbr\u003e\u003cbr\u003e接下来一行包含 M 个整数,表示宝石的价值。\u003cbr\u003e\u003cbr\u003e接下来的 H 行将包含 W 个字符。它们代表以下符号的地牢地图:\u003cbr\u003e\u0026gt; [*] 代表墙壁,你无法移动到其中;\u003cbr\u003e\u0026gt; [.] 代表空格,你可以移动到其中;\u003cbr\u003e\u0026gt; [@] 代表冒险者的初始位置;\u003cbr\u003e\u0026gt; [\u0026lt;] 代表出口楼梯;\u003cbr\u003e\u0026gt; [A] - [J] 代表宝石。\u003cbr\u003e"}},{"title":"输出","value":{"format":"HTML","content":"结果应输出到标准输出。每个测试用例以单独一行的形式以 \"Case #:\" 开始,其中 # 是从 1 开始的测试用例编号。连续的两个测试用例之间应有一个空行分隔。在最后一个测试用例之后不应产生空行。\u003cbr\u003e\u003cbr\u003e如果冒险者能在规定时间内到达出口楼梯,打印句子 \"The best score is S.\",其中 S 是他沿途可以收集到的宝石的最大价值;否则在单独一行上打印单词 \"Impossible\"。\u003cbr\u003e"}},{"title":"样例","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\u003e3\r\n\r\n4 4 2 2\r\n100 200\r\n****\r\n*@A*\r\n*B\u0026lt;*\r\n****\r\n\r\n4 4 1 2\r\n100 200\r\n****\r\n*@A*\r\n*B\u0026lt;*\r\n****\r\n\r\n12 5 13 2\r\n100 200\r\n************\r\n*B.........*\r\n*.********.*\r\n*@...A....\u0026lt;*\r\n************\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase 1:\r\nThe best score is 200.\r\n\r\nCase 2:\r\nImpossible\r\n\r\nCase 3:\r\nThe best score is 300.\r\n\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}