Buszok
Egy városban az úthálózat csupa észak-dél és kelet-nyugat irányú útból áll. A helyi tömegközlekedés R buszjáratból áll. A járatok rögzített útvonalon közlekednek, minden kereszteződésben van megálló. (A kereszteződés az, ahol az egymásra merőleges utak metszik egymást.) Minden útvonalon pontosan egy busz jár, mindegyik járaton külön ára van a buszjegynek, de egy járaton bármennyit lehet utazni a jeggyel. Átszálláskor viszont új jegyet kell venni.
Néha persze gyalogolni is kell, hiszen nem mindegyik kereszteződésen halad át buszjárat útvonala. A séta is ugyanazokon az utcákon történhet, ahol a buszok járnak, nincsenek érdekes rövidítések.
Egy turista A-ból B-be szeretne eljutni, de mivel nyaral, legfeljebb D távolságot szeretne gyalogolni. (Két szomszédos kereszteződés távolsága az egység.) Ráadásul a lehető legolcsóbban akarja megoldani az utazást.
Feladat
Írj programot, ami megadja a legolcsóbb út árát, vagy kiírja, hogy "LEHETETLEN", ha nincs megoldása a feladatnak.
Bemenet
- az első sor $D$ értékét adja meg $(0 \leq D \leq 300)$
- a második sor $A$ koordinátáit
- a harmadik $B$ koordinátáit írja le
- a koordináták 1 és 100,000,000 közé esnek
- $A$ és $B$ különböző
- a negyedik sor $R$ értékét adja meg $(1 \leq R \leq 100)$, tehát a buszjáratok számát
- a következő $R$ sor egy-egy buszjáratot ír le a következő számokkal:
- $N$ $(4 \leq N \leq 50)$, a járat útvonalát leíró pontok száma (ahol kanyarodik)
- $f$ a jegyár az adott járaton $(0 \leq f \leq 1,000,000)$
- majd $N$ számpár, a kanyarok koordinátái
- a kanyarok között egyenesen halad a busz, a kanyarok 90°-osak
Kimenet
A kimenet egyetlen sora a legolcsóbb utazás árát, vagy a "LEHETETLEN" szót tartalmazza.
Példák és egyben tesztadatok
| BUSZ.BE | BUSZ.KI |
4 3 7 13 1 2 6 2 14 8 5 8 5 6 11 6 11 3 14 3 4 5 16 4 7 4 7 2 16 2 |
2 |
| BUSZ.BE | BUSZ.KI |
2 1 5 10 7 3 4 10 1 4 5 4 5 6 1 6 4 10 5 5 5 7 7 7 7 5 4 20 9 5 9 1 7 1 7 5 | LEHETETLEN |