{"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\"\u003eMột ngày nọ, một thợ săn tên là James đi vào một khu vực bí ẩn để tìm kiếm kho báu. James muốn nghiên cứu khu vực và mang về tất cả kho báu mà anh ta có thể.\u003cbr\u003e Khu vực có thể được biểu diễn dưới dạng hình chữ nhật N*M. Bất kỳ điểm nào của hình chữ nhật đều là một số có nghĩa là chi phí để nghiên cứu nó, -1 có nghĩa là James không thể vượt qua nó, James có thể bắt đầu ở bất kỳ nơi nào ngoài hình chữ nhật, và khám phá từng điểm một. Anh ta sẽ di chuyển trong hình chữ nhật và mang về tất cả kho báu mà anh ta có thể mang. Tất nhiên, anh ta sẽ kết thúc ở bất kỳ biên nào để ra khỏi hình chữ nhật (James sẽ nghiên cứu mọi điểm mà anh ta đi qua bởi vì anh ta không nhớ liệu điểm đó đã được nghiên cứu hay chưa).\u003cbr\u003e Bây giờ bạn hãy cho bạn một bản đồ của khu vực, bạn phải tính toán chi phí ít nhất mà James mang về tất cả kho báu mà anh ta có thể mang (mỗi điểm chỉ có thể có một kho báu). Ngoài ra, nếu không có gì mà James có thể lấy, hãy đầu ra 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":"Nhập","value":{"format":"HTML","content":" Đầu vào bao gồm T bộ test. Số lượng bộ test T được cho trên dòng đầu tiên của đầu vào. Mỗi bộ test bắt đầu bằng một dòng chứa 2 số nguyên N M, (1≤N,M≤200), đại diện cho hình chữ nhật. Mỗi trong số N dòng tiếp theo chứa M số (0~9), đại diện cho chi phí của mỗi điểm. Tiếp theo là K(1≤K≤13), và tiếp theo là K dòng, mỗi dòng chứa 2 số nguyên x y đại diện cho vị trí của kho báu, x đại diện cho hàng và bắt đầu từ 0, y đại diện cho cột cũng bắt đầu từ 0."}},{"title":"Đầu ra","value":{"format":"HTML","content":" Đối với mỗi bộ test, bạn chỉ cần đầu ra một số duy nhất đại diện cho chi phí tối thiểu."}},{"title":"Ví dụ","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"}}]}