{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"\u003cp\u003eSki season is in full swing and the Chef decided it\u0027s time to expand his business. He invested into a restaurant at the bottom of a ski slope. Things were going great until one of his employees got injured while skiing home from work. Chef would like to make sure this doesn\u0027t happen again. He wants to alter the surrounding landscape to prevent his employees from skiing to their homes in the nearby town. Flattening a large area is obviously out of the question and that\u0027s where you come in.\n\n\u003c/p\u003e\u003cp\u003eChef was kind enough to model the surronding area as a grid with H rows and W columns. Area outside this grid is not suitable for skiing. You are given the elevation of each cell in this grid and the location of his restaurant (Rr,Cr) and the town (Rt,Ct). As long as there exists a non-increasing path from the restaurant to the town, the employees will not hesitate to ski home. A sequence of cells is called a path if every consecutive pair of cells shares a common edge. You are allowed to \u003cb\u003eincrease\u003c/b\u003e the elevation of any cell (except for the restaurant and town cell) by an integer amount. Find the minimum total number of units of elevation increase\nwhich allows Chef to prevent his employees from skiing home.\n\n\u003ch3\u003eInput\u003c/h3\u003e\n\u003c/p\u003e\u003cp\u003eThe first line contains a single integer T, the number of test cases. The first line of each testcase contains numbers H and W. Rr, Cr, Rt, Ct are given in the second line. Following lines describe the layout of the ski resort. The j-th number in the i-th line represents elevation E\u003csub\u003ei,j\u003c/sub\u003e of cell (i,j). Top left corner of the grid has coordinates (1,1). All numbers in the input are integer.\n\n\u003ch3\u003eOutput\u003c/h3\u003e\n\u003c/p\u003e\u003cp\u003eFor each test case, output minimum total elevation so that chef can achieve his goal or -1 if that is not possible.\n\n\u003ch3\u003eConstraints\u003c/h3\u003e\n\u003cul\u003e\n\u003cli\u003eT \u003c\u003d 10\u003c/li\u003e\n\u003cli\u003e1 \u003c\u003d H,W \u003c\u003d 50\u003c/li\u003e\n\u003cli\u003e0 \u003c\u003d E\u003csub\u003ei,j\u003c/sub\u003e \u003c\u003d 200 000\u003c/li\u003e\n\u003c/ul\u003e\n\n\u003ch3\u003eExample\u003c/h3\u003e\n\n\u003cpre\u003e\n\u003cb\u003eInput:\u003c/b\u003e\n2\n\n4 2\n1 1 3 2\n10 11\n6 6\n4 4\n3 4\n\n1 5\n1 2 1 3\n3 4 2 5 5\n\n\u003cb\u003eOutput:\u003c/b\u003e\n4\n-1\n\u003c/pre\u003e\u003c/p\u003e"}}]}