{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n section pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"Problem Statement","value":{"format":"HTML","content":"\r\n\u003csection\u003e\r\n\u003cp\u003eThe Kingdom of Takahashi can be represented as a grid with \u003cvar\u003e\\(H\\)\u003c/var\u003e rows and \u003cvar\u003e\\(W\\)\u003c/var\u003e columns. Let \u003cvar\u003e\\((i, j)\\)\u003c/var\u003e denote the square at the \u003cvar\u003e\\(i\\)\u003c/var\u003e-th row from the north and \u003cvar\u003e\\(j\\)\u003c/var\u003e-th column from the west.\u003c/p\u003e\r\n\u003cp\u003eRecently, there have been more and more requests from the kingdom\u0027s citizens to build a railway, and now the king, Takahashi, has no choice but to build one.\u003cbr\u003e\r\nThe construction of the railway will have the following two phases.\u003c/p\u003e\r\n\u003cul\u003e\r\n\u003cli\u003eFirst, choose two \u003cstrong\u003edifferent\u003c/strong\u003e squares and build a station on each of them. It costs \u003cvar\u003e\\(A_{i,j}\\)\u003c/var\u003e yen to build a station on the square \u003cvar\u003e\\((i, j)\\)\u003c/var\u003e.\u003c/li\u003e\r\n\u003cli\u003eThen, build a railway track connecting these two stations. This costs \u003cvar\u003e\\(C \\times (|i-i\u0027| + |j-j\u0027|)\\)\u003c/var\u003e yen when the two stations are on the squares \u003cvar\u003e\\((i, j)\\)\u003c/var\u003e and \u003cvar\u003e\\((i\u0027, j\u0027)\\)\u003c/var\u003e. (\u003cvar\u003e\\(|x|\\)\u003c/var\u003e denotes the absolute value of \u003cvar\u003e\\(x\\)\u003c/var\u003e.)\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003cp\u003eTakahashi\u0027s priority is to spend as little as possible on this construction, rather than to improve convenience for the citizens.\u003cbr\u003e\r\nPrint the minimum possible total cost of the construction of the railway.\u003c/p\u003e\r\n\u003c/section\u003e\r\n"}},{"title":"Constraints","value":{"format":"HTML","content":"\r\n\u003csection\u003e\r\n\u003cul\u003e\r\n\u003cli\u003e\u003cvar\u003e\\(2 \\leq H, W \\leq 1000\\)\u003c/var\u003e\u003c/li\u003e\r\n\u003cli\u003e\u003cvar\u003e\\(1 \\leq C \\leq 10^9\\)\u003c/var\u003e\u003c/li\u003e\r\n\u003cli\u003e\u003cvar\u003e\\(1 \\leq A_{ij} \\leq 10^9\\)\u003c/var\u003e\u003c/li\u003e\r\n\u003cli\u003eAll values in input are integers.\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003c/section\u003e\r\n"}},{"title":"Input","value":{"format":"HTML","content":"\r\n\u003csection\u003e\r\n\u003cp\u003eInput is given from Standard Input in the following format:\u003c/p\u003e\r\n\u003cpre\u003e\u003cvar\u003e\\(H\\)\u003c/var\u003e \u003cvar\u003e\\(W\\)\u003c/var\u003e \u003cvar\u003e\\(C\\)\u003c/var\u003e\r\n\u003cvar\u003e\\(A_{1,1}\\)\u003c/var\u003e \u003cvar\u003e\\(A_{1,2}\\)\u003c/var\u003e \u003cvar\u003e\\(\\cdots\\)\u003c/var\u003e \u003cvar\u003e\\(A_{1,W}\\)\u003c/var\u003e\r\n\u003cvar\u003e\\(\\vdots\\)\u003c/var\u003e\r\n\u003cvar\u003e\\(A_{H,1}\\)\u003c/var\u003e \u003cvar\u003e\\(A_{H,2}\\)\u003c/var\u003e \u003cvar\u003e\\(\\cdots\\)\u003c/var\u003e \u003cvar\u003e\\(A_{H,W}\\)\u003c/var\u003e\r\n\u003c/pre\u003e\r\n\u003c/section\u003e\r\n"}},{"title":"Output","value":{"format":"HTML","content":"\r\n\u003csection\u003e\r\n\u003cp\u003ePrint the minimum possible total cost of the construction of the railway.\u003c/p\u003e\r\n\u003c/section\u003e\r\n"}},{"title":"Sample 1","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 4 2\r\n1 7 7 9\r\n9 6 3 7\r\n7 8 6 4\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e10\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\r\n\u003csection\u003e\r\n\r\n\u003c/section\u003e\r\n\r\n\u003csection\u003e\r\n\r\n\u003cp\u003eIf we build stations on the squares \u003cvar\u003e\\((1, 1)\\)\u003c/var\u003e and \u003cvar\u003e\\((2, 3)\\)\u003c/var\u003e, it will cost \u003cvar\u003e\\(1 + 3 \u003d 4\\)\u003c/var\u003e yen to build the stations and \u003cvar\u003e\\(2 \\times (|1-2| + |1-3|) \u003d 6\\)\u003c/var\u003e yen to build the track, for a total of \u003cvar\u003e\\(4+6 \u003d 10\\)\u003c/var\u003e yen.\r\nThis is the minimum possible total cost of the construction.\u003c/p\u003e\r\n\u003c/section\u003e\r\n"}},{"title":"Sample 2","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 3 1000000000\r\n1000000 1000000 1\r\n1000000 1000000 1000000\r\n1 1000000 1000000\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1001000001\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\r\n\u003csection\u003e\r\n\r\n\u003c/section\u003e\r\n\r\n\u003csection\u003e\r\n\u003c/section\u003e\r\n"}}]}