Bajtazar Bajtock, słynny podróżnik, postanowił wybrać się w podróż poprzez najwyższe bajtockie góry: Bajtalaje. Pasmo to jest jedną z największych ciekawostek geograficznych ponieważ jest bardzo regularnie zbudowane: gdyby stworzyć mapę i podzielić ją odpowiednio na równe kwadraty to można by w każdym z tych kwadratów narysować szczyt natomiast pomiędzy szczytami w pionie i poziomie można by zaznaczyć przełęcze, którymi można się poruszać. Z każdego szczytu można zatem przejść do szczytu znajdującego się na mapie jedną pozycję w górę, w dół, w prawo lub w lewo. Jakakolwiek inna droga nie wchodzi w rachubę ponieważ Bajtalaje aż roją się od urwisk, ukrytych pod śniegiem jaskiń i wszelkich innych niebezpieczeństw.
Ponieważ czas wielkiego podróżnika jest bardzo cenny postanowił on poszukać najszybszej z możliwych dróg prowadzących poprzez góry. Zamówiony już helikopter zrzuci go w wybrane miejsce (któryś ze szczytów lewym krańcu mapy) i odbierze z dowolnego ze szczytów na prawym krańcu. Podróżnik podczas swojej wędrówki będzie poruszał się w dół, w górę oraz w prawą stronę mapy, natomiast nie będzie nigdy poruszał się w lewo – gdyż bajtalajscy mnisi, których rady zasięgnął pan Bajtock powiedzieli mu, że może to sprowadzić złe moce. Ponadto wędrowiec nie chce nigdy zejść z gór – nie jest więc możliwe, że znajdzie się poza obszarem mapy.
Czas przemarszu pomiędzy dwoma szczytami stanowi wartość 1 + wartość bezwzględna różnicy w ich wysokościach – nie ma więc różnicy czy schodzimy w dół czy wchodzimy pod górę.
Ponieważ Bajtazar Bajtock jest wybitnym podróżnikiem, nie chce zajmować się tak trywialną rzeczą jak poszukiwanie najszybszej drogi i zlecił ją Tobie w zamian za wypożyczenie kolekcji zdjęć z jego ostatniej podróży w dorzecze Bajtazonki. Ponieważ aby wykonać zadanie potrzebny była ci mapa, odszukałeś takową w jednej z bibliotek. Niestety po przybyciu do domu stwierdziłeś, że owszem, mapa opisuje Bajtalaje ale za pomocą notacji stosowanej przez bajtalajskich mnichów. W notacji tej cała mapa zapisana jest w postaci liczb. Pierwsze dwie liczby to rozmiar mapy – liczba wierszy i kolumn tablicy z wysokościami szczytów. Trzecia liczba to wysokość wszystkich szczytów nieopisanych formułami znajdującymi się poniżej. Następne liczby tworzą formuły – każda formuła ma dokładnie 6 liczb. Każdy opis mapy kończy się formułą, w której wszystkie liczby równe są 0. Postać formuły jest następująca: pierwsza liczba to wysokość szczytów, których współrzędne wyznacza się za pomocą dalszej części formuły; następne dwie liczby to współrzędne x i y (kolumna i wiersz) punktu początkowego – pierwszego szczytu o zadanej wysokości. Następne dwie liczby to wartości, które dodaje się do współrzędnych celem wyznaczenia współrzędnych kolejnego szczytu – wartości te muszą być brane modulo odpowiednio: szerokość i wysokość mapy. Ostatnia liczba to ilość szczytów opisywanych przez formułę ze szczytem początkowym włącznie. Kolejność formuł jest ważna – wyniki płynące z formuł późniejszych mogą nadpisywać wyniki płynące z formuł wcześniejszych.
Ponieważ trasa musi pozostać tajna (ze względów bezpieczeństwa) jako odpowiedź dla zestawów danych twój program zwraca tylko koszt przejścia najszybszej drogi.
Na wejście programu zostanie podanych pewna liczba zestawów danych.
Każdy zestaw składa się z następujących danych: pierwsza linia zawiera szerokość W i wysokość H mapy (1 ≤ W ≤ 2200, 1 ≤ H ≤ 2200). Kolejna linia zawiera jedną liczbę Z będącą wysokością wszystkich nieopisanych formułami szczytów (1 ≤ Z < 230). Kolejne linie zawierają formuły zgodne z opisem w treści – każda formuła posiada 6 liczb: V, SX, SY, DX, DY, M o zakresach odpowiednio: 0 ≤ V < 230; 0 ≤ SX < W; 0 ≤ SY < H; 0 ≤ DX < 230; 0 ≤ DY < 230; 1 ≤ M < 230. Lista formuł, jak opisano powyżej, kończy się formułą zawierającą same zera; liczba wszystkich formuł, nie wliczając formuły z samymi zerami nie przekracza 200. Dane kończą się zestawem, w którym szerokość i wysokość mapy jest równa 0 – za tymi zerami nie ma już więcej danych – dla tego zestawu nie wyznacza się wyników!
Dla każdego zestawu danych należy wypisać jedną linię zawierającą liczbę będącą kosztem najkrótszej ścieżki.
6 4 2 5 1 1 1 3 6 3 3 2 7 5 5 0 0 0 0 0 0 20 15 1000 1001 0 0 17 13 100 1002 1 1 19 11 100 1003 2 2 11 13 100 0 0 0 0 0 0 0 0
9 41
5 2 5 2 2 3 3 5 2 2 2 5 2 3 2 3 5 2 2 2 2 5 3 2