{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cstyle type\u003d\u0027text/css\u0027\u003e .input, .output {border: 1px solid #888888;} .output {margin-bottom:1em;position:relative;top:-1px;} .output pre,.input pre {background-color:#EFEFEF;line-height:1.25em;margin:0;padding:0.25em;} .title {background-color:#FFFFFF;border-bottom: 1px solid #888888;font-family:arial;font-weight:bold;padding:0.25em;} \u003c/style\u003e \u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027]], displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027]]}\n });\n \u003c/script\u003e\n \u003cscript type\u003d\"text/javascript\" async\n src\u003d\"https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\"\u003e\n \u003c/script\u003e\n\n\u003cp\u003eElrond calls a war council. On the table of the war-council meeting room is a rectangular map of Mordor on an N x M grid. Each cell of the grid shows the number of Orcs in it. The top left corner of the board represents Mount Doom, and the bottom right is Frodo\u0027s planned entry point into Mordor. Frodo\u0027s path through Mordor corresponds to moves on the map starting at the bottom right cell and moving towards the top right cell via adjacent squares. (i.e. Can move from any cell to the 4 adjacent cells. Cannot move diagonally)\u003c/p\u003e \n\n\u003cp\u003eIf Frodo occupies a particular cell, he attracts the attention of all orcs in that cell. Help Elrond compute the minimum number of Orcs that Frodo is noticed by to get to his destination at Mount Doom. \u003c/p\u003e\n\n"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe input file consists of many such maps. The first line has a single integer k denoting the number of maps. The next 2 lines contain integers N and M defining the size of the map. The number of Orcs in each cell is then given as an NxM matrix in the next N lines. After that, the data of the next map follows in the same manner.\u003c/p\u003e. "}},{"title":"Output","value":{"format":"HTML","content":"For each map, output the minimum number of Orcs to be faced in that map. Make sure that answers for different maps are on different lines."}},{"title":"Constraints","value":{"format":"HTML","content":"1 ≤ Number of maps k ≤ 100 \u003cbr\u003e\n0 ≤ Number of orcs in each cell in any given map ≤ 9 \u003cbr\u003e\nNumber of cells in a map (i.e. map size) ≤ 999 x 999\n"}},{"title":"Sample Input ","value":{"format":"HTML","content":"2 \u003cbr\u003e\n4 \u003cbr\u003e\n5 \u003cbr\u003e\n0 3 1 2 9 \u003cbr\u003e\n7 3 4 9 9 \u003cbr\u003e\n1 7 5 5 3 \u003cbr\u003e\n2 3 4 2 5 \u003cbr\u003e\n1 \u003cbr\u003e\n6 \u003cbr\u003e\n0 1 2 3 4 5 \u003cbr\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"24 \u003cbr\u003e\n15"}}]}