{"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 Местность может быть представлена в виде прямоугольника N*M. Любая точка прямоугольника представляет собой число, обозначающее стоимость ее изучения, -1 означает, что Джеймс не может пройти через эту точку. Джеймс может начать с любого места за пределами прямоугольника и исследовать точку за точкой. Он будет двигаться в пределах прямоугольника и забирать все сокровища, которые только сможет найти. Конечно же, он закончит свое исследование на любой границе, чтобы выйти из прямоугольника (Джеймс будет изучать каждую точку в любое время, когда он проходит мимо, потому что он не может запомнить, изучена ли уже эта точка или нет).\u003cbr\u003e Теперь у вас есть карта местности, вы должны рассчитать минимальную стоимость, которую Джеймс заплатит, чтобы забрать все сокровища, которые только сможет найти (одно место может содержать только одно сокровище). Также, если Джеймс ничего не сможет найти, пожалуйста, выведите 0.\u003cbr\u003e\u003ccenter\u003e\u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/9b18be8549c8a7df4b1f759e2cf6e5f3?v\u003d1701341671\"\u003e\u003c/center\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":" Ввод состоит из T тестов. Количество тестов T указано в первой строке ввода. Каждый тест начинается с строк, содержащей 2 целых числа N M, (1\u0026lt;\u003dN,M\u0026lt;\u003d200), которые представляют прямоугольник. Каждая из следующих N строк содержит M чисел (0~9), представляющих стоимость каждой точки. Затем идет K(1\u0026lt;\u003dK\u0026lt;\u003d13), и далее K строк, каждая строка содержит 2 целых числа x y, означающие положение сокровищ, x означает строку и начинается с 0, y означает столбец и также начинается с 0."}},{"title":"Output","value":{"format":"HTML","content":" Для каждого теста вы должны вывести только одно число, означающее минимальную стоимость."}},{"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\u003e2\r\n3 3\r\n3 2 3\r\n5 4 3\r\n1 4 2\r\n1\r\n1 1\r\n3 3\r\n3 2 3\r\n5 4 3\r\n1 4 2\r\n2\r\n1 1\r\n2 2\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e8\r\n11\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}