Egy föld alatti barlangrendszerben kajakozol, amikor rádöbbensz, hogy érkezik a dagály, ezért csapdába kerültél. Szerencsére van egy térképed a barlangról. Egészen addig várnod kell, amíg elkezdődik az apály, ezért lesz időd átgondolni, hogy mi lesz a leggyorsabb módja a menekülésnek (az apály kezdetétől számolva).

A barlang térképe két N x M-es táblázatból áll. Az első a plafon magasságát adja meg minden "cellában", a második pedig a padló magasságát. A padló olyan anyagból van, hogy átereszti a vizet, ezért a vízszint csökkenésekor sehol nem marad víz a vízszint felett, akkor sem, ha a padló magasabban van.

A térkép észak-nyugati sarkában estél csapdába. Pillanatnyilag H centiméter a víz magassága, ami az apály kezdetétől másodpercenként 10 cm-rel csökken, amíg el nem éri a 0-át. A kijárat a dél-keleti sarokban van, ami pillanatnyilag víz alatt áll, de az apály kezdete után járhatóvá válik. 

Bármely pillanatban négy irányba tudsz lépni, (É, K, D, NY) a következő feltételek mellett:

• A vízszint, az aktuális mező padlójának szintje és a szomszédos mező padlójának szintje legalább 50 cm-rel kevesebb mint a szomszédos mező plafonjának szintje. Megjegyzés: ez azt jelenti, hogy olyan mezőre sosem tudunk lépni, amelynek plafonja és padlója között 50 cm-nél kevesebb a távolság. 
• A szomszédos mező padlója legalább 50 cm-rel lejjebb van, mint az aktuális mező plafonja.
• A térképről nem szabad lelépni.

• Az első ábrán nincs meg az 50 cm a szomszédos plafon és a vízszint között, ezért nem tudsz átlépni. 
• A második ábrán az a baj, hogy a szomszédos plafon és az aktuális padló között nincs meg az 50 cm.
• A harmadik ábrán a szomszédos mező plafonjának és padlójának távolsága túl kicsi. Egy ilyen mezőre soha nem tudunk rálépni, a vízszinttől függetlenül.
• A negyedik ábrán azért nem tudsz jobbra lépni, mert az aktuális plafon és a szomszédos padló között túl kicsi a távolság. 

Ha egy mezőről olyankor lépsz át a szomszédosra, amikor az aktuális mezőn még legalább 20 cm víz van a padló szintje fölött, akkor 1 másodperc alatt átérsz a szomszédos mezőre (használhatod a kajakot). Egyébként 10 másodperc egy lépés, mert kézben kell vinned a kajakodat.  Ez az idő csak a kiindulási mező vízszintjétől függ. 

Egy ideig el fog tartani, amíg a víz apadni kezd, és addig tetszőlegesen mozoghatsz a barlangban. Csak az számít, hogy az apály kezdetétől számítva mennyi idő kell a szabaduláshoz. Ki tudod ezt számítani?

Megjegyzés

Elképzelhető, hogy végig tudsz menni a teljes barlang-rendszeren az apály kezdete előtt. Ebben az esetben a kijáratnál várhatod meg a vízszint csökkenését, és így 0 idő alatt kijutsz, az apály kezdetétől számolva. 

Feladat

Írjunk programot, ami megadja, hogy az apály kezdetétől számolva mennyi idő kell ahhoz, hogy kijussunk a barlangból.

Bemenet

• Az első sor a tesztesetek T számát tartalmazza.
• Ezután T teszteset következik, amelyek mindegyike egy három számot tartalmazó sorral kezdődik: H, N és M, a kezdeti vízszint, és a térkép dimenziói. A következő 2N sor a padló és a plafon magasságot adja meg az alábbiak szerint:
  • Először  N sor mindegyike  M szóközökkel elválasztott egészt tartalmaz. A j. szám az i. sorban C_ij, a plafon magassága a (j, i) koordinátájú cellában. (Az i dél felé, a j kelet felé nő.)
  • Ezután  N sorban a padló magasságok (Fji) vannak megadva, az előzővel azonos formátumban.
• A kiinduló mezőn kezdetben biztosan lesz 50 cm a vízszint és a plafon, illetve a padló és a plafon között.
• A kijáratnál lesz legalább 50 cm a padló és a plafon között.
• Mindig lesz kiút (elvégre valahogy be is jutottál a barlangba).

Kimenet

Minden tesztesethez egyetlen (tört) számot kell megadni, ami akkor helyes, ha legfeljebb 10^-6 az eltérése a pontos választól.

Méretek

Kis bemenet

1 ≤ T ≤ 50. 
1 ≤ N, M ≤ 10. 
1 ≤ H ≤ 1000. 
1 ≤ F_xy ≤ C_xy ≤ 1000.

Nagy bemenet

1 ≤ T ≤ 50. 
1 ≤ N, M ≤ 100. 
1 ≤ H ≤ 10000. 

1 ≤ F_xy ≤ C_xy ≤ 10000.

Példa

Bemenet	Kimenet
4 200 1 2 250 233 180 100 100 3 3 500 500 500 500 500 600 500 140 1000 10 10 10 10 10 490 10 10 10 100 3 3 500 100 500 100 100 500 500 500 500 10 10 10 10 10 10 10 10 10 100 2 2 1000 1000 1000 1000 100 900 900 100	Case #1: 11.7 Case #2: 3.0 Case #3: 18.0 Case #4: 0.0

Tesztadatok

tide-small.in    tide-small.out    tide-large.in    tide-large.out

Címkék

A feladat forrása: Google Code Jam 2012, Round 1B, https://code.google.com/codejam/contest/1836486/dashboard#s=p1

Algoritmusok: Dijkstra-algoritmus

megoldás