Šeštadieninė informatikos olimpiadininkų mokykla

Prie vieno seno namo Antakalny, kuriame gyvena Linas, yra tujomis apsodinta mašinų stovėjimo aikštelė, sudaryta iš 6x6 langelių gardelės. Aikštelės eilutės yra sunumeruotos nuo 1 iki 6 iš viršaus į apačią, o stulpeliai - tuo pačiu būdu iš kairės į dešinę. Trečios eilės dešinėje pusėje yra vienintelis išvažiavimas iš aikštelės.

Kiekvieną rytą Linas šioje aikštelėje randa savo mašinytę užblokuotą kitų automobilių. Laimei, Lino kaimynai savo automobilius palieka įjungę neutralią pavarą, todėl Linas gali juos stumdyti pirmyn ir atgal, tačiau jis negali automobilių vairuoti, net ir savo paties mašinytės, kol ji aikštelėje. Automobiliai stovėjimo aikštelėje yra įvairaus dydžio: vieni užima 2x1 gardelės langelių, o kiti - 3x1. Lino mašinytė yra 2x1 dydžio. Automobiliai gali būti judinamos tik ilgesniosios ašies kryptimi.

Jūs turite rasti, kiek mažiausiai pastūmimų Linui pakaks savo mašinytei išstumti iš aikštelės. Vienu pastūmimu vadinamas vieno automobilio pastūmimas per vieną langelį. Nei vienas iš automobilių negali būti išstumiamas iš aikštelės.

Pateiktame paveiksle yra N = 8 automobiliai, Lino mašinytė pažymėta numeriu 1. Mažiausias pastūmimų skaičius, kurio pakaktų Linui išstumti savo mašinytę iš aikštelės, yra 18: 4←←←,2→,6↑,3↑,8←←,5↓↓↓,7↓↓,1→→→→→.

Pradiniai duomenys

Pirmoje pradinių duomenų failo eilutėje įrašytas automobilių skaičius N ().

Tolesnėse N eilučių aprašomi automobiliai, kurių numeriai i=1,2,...,N. Kiekvienoje eilutėje įrašyti keturi sveikieji skaičiai. Pirmasis jų automobilio ilgis (užimamų kvadratų skaičius) li, orientacija oi, ir pirmojo (t.y. viršutinio kairiojo) kvadrato, kurį užima automobilis, koordinatės xi (stulpelis) ir yi (eilutė). Tarp skaičių palikta po vieną tarpą. oi=1 reiškia, kad automobilis pastatytas horizontaliai, kitu atveju – kad vertikaliai. Galioja tokie ribojimai: ∈ {2,3}, ∈ {0,1}, .

Lino mašinytės numeris yra 1 (taigi jis aprašytas antroje failo eilutėje). Lino mašinytę reikia išstumti iš aikštelės pro vienintelį išėjimą.

Rezultatai

Į rezultatų failą turi būti įrašomas mažiausias įmanomas pastūmimų skaičius. Jei Lino mašinytės išstumti iš aikštelės neįmanoma, įrašykite –1.

Pavyzdys

8
2 1 2 3
2 1 1 1
2 0 1 5
2 1 5 5
3 0 6 1
3 0 1 2
3 0 4 2
3 1 3 6

18