Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Duomenų failas: kauliukas.in

Rezultatų failas: kauliukas.out

Jei norite pateikti savo sprendimą - prisijunkite.

Kauliuko kelionė

Artėja Dominyko gimtadienis. Kad vakaras su draugais neprailgtų, Dominykas nusprendė paruošti įvairių stalo žaidimų. Kelis žaidimus jis net sugalvojo pats! Dominykas norėtų Jums paaiškinti savo žaidimo, pavadinto „Kauliuko kelionė“, taisykles:

Žaidimas vyksta stačiakampiame languotame popieriaus lape (žaidimo lentoje), kurio kiekviename langelyje įrašytas sveikasis skaičius iš intervalo [1, 6]. Žaidžiama standartiniu lošimo kauliuku (žr. akučių išdėstymą pav. dešinėje). Lentos langelio ir kauliuko šono matmenys sutampa, todėl pastatytą kuriame nors langelyje kauliuką pavertus ant vieno iš keturių šonų, jis atsiduria gretimame langelyje. Šitoks kauliuko perkėlimas į gretimą langelį (kauliuką paverčiant) yra vadinamas ėjimu. Jokie kiti veiksmai su kauliuku (pavyzdžiui, kauliuko pasukimas) neleistini.

Du lentelės langeliai pažymėti ypatingai. Žaidimo tikslas – atliekant kuo mažiau ėjimų lošimo kauliuką perkelti iš pirmojo langelio į antrąjį. Štai pagrindinė žaidimo taisyklė: po kiekvieno ėjimo kauliukas turi būti atsivertęs tokiu akučių skaičiumi, koks įrašytas langelyje, kuriame jis stovi.

Statydamas kauliuką į pradinį langelį, žaidėjas privalo laikytis minėtosios taisyklės, tačiau gali pasukti kauliuką, kaip nori.

Dominykas labai didžiuojasi savo sugalvotu žaidimu. Jis jau paruošė žaidimo lentą. Gimtadienio metu draugai rungtyniaus, kuriam pavyks perkelti kauliuką mažesniu ėjimų skaičiumi. Kadangi paruošta žaidimo lenta yra didelė, Dominykas nėra tikras, ar jam žinomas sprendimas yra geriausias. Kaip žaidimo autorius, jis norėtų žinoti, kiek mažiausiai ėjimų pakanka kauliukui perkelti iš pradinio langelio į galinį. Parašykite programą, kuri išspręstų šį uždavinį Dominykui.

Pradiniai duomenys

Pirmoje eilutėje įrašyti du sveikieji skaičiai N ir M (2\\leN,M\\le100). N yra žaidimo lentos stulpelių, o M – eilučių skaičius. Lentos eilutės sunumeruotos nuo 1 iki M, o stulpeliai – nuo 1 iki N.

Antroje eilutėje įrašyti keturi sveikieji skaičiai x_a, y_a, x_b ir y_b (1\\lex_a,x_b\\leN, 1\\ley_a,y_b\\leM). (x_a,y_a) yra pradinio langelio, o (x_b,y_b) – galinio langelio koordinatės (x reiškia stulpelio, o y – eilutės numerį). Pradinis ir galinis langeliai yra skirtingi.

Tolesnėse M eilučių pateikta pati skaičių lentelė – po N skaičių kiekvienoje eilutėje. Visi skaičiai yra sveikieji skaičiai iš intervalo [1, 6].

Rezultatai

Vienintelėje eilutėje turi būti įrašytas vienintelis sveikasis skaičius K – mažiausias ėjimų skaičius, kurio pakanka kauliukui perkelti iš pradinio langelio į galinį. Dominykas užtikrina, kad kauliuką perkelti yra įmanoma.

Pavyzdžiai

Duomenys Rezultatai 
2 2
1 1 1 2
1 2
1 4
 
3
 
5 3
1 2 5 2
4 3 6 3 1
1 2 2 2 6
3 4 1 4 2
 
8
 
5 5
1 1 5 1
1 1 1 6 4
3 5 1 2 4
6 3 6 2 1
4 5 3 3 4
1 2 6 5 1
 
12