Ski Resort

Problem code: SKIRES

All submissions for this problem are available.

Ski season is in full swing and the Chef decided it's 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't 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's where you come in.

Chef 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 increase 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 which allows Chef to prevent his employees from skiing home.

Input

The 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 Ei,j of cell (i,j). Top left corner of the grid has coordinates (1,1). All numbers in the input are integer.

Output

For each test case, output minimum total elevation so that chef can achieve his goal or -1 if that is not possible.

Constraints

  • T <= 10
  • 1 <= H,W <= 50
  • 0 <= Ei,j <= 200 000

Example

Input:
2

4 2
1 1 3 2
10 11
6 6
4 4
3 4

1 5
1 2 1 3
3 4 2 5 5

Output:
4
-1

Author: thocevar
Date Added: 2-12-2010
Time Limit: 7 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC


Comments

Please, explain first sample.

aircube @ 1 Mar 2011 05:40 PM

Please, explain first sample.

Please Explain it ...??

devrajchouhan @ 2 Mar 2011 10:17 PM

Please Explain it ...??

Figuring out the provided

tomaz_adm @ 3 Mar 2011 01:52 AM

Figuring out the provided example is part of the problem.

0 <= final elevation <= 200

ytau @ 6 Mar 2011 12:49 PM

0 <= final elevation <= 200 000 , yes or no?

@Tsun: Why would you assume

tomaz_adm @ 6 Mar 2011 05:54 PM

@Tsun: Why would you assume that? Problem statement limits only initial elevations, the rest is up to you.

Can we increase the elevation

pulkit @ 8 Mar 2011 08:01 AM

Can we increase the elevation of only 1 cell or any number of cells?

Any number of cells, check

tomaz_adm @ 8 Mar 2011 12:48 PM

Any number of cells, check the first example.

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

CodeChef is a global programming communityCodeChef hosts online programming competitions