Ulice

Bedřich je na návštěvě u Jiřího ve městě, kam se Jiří nedávno přestěhoval. Plánují, že než půjdou odpoledne do kina, Jiří proveze Bedřicha městem a ukáže mu všechny ulice. Ulice jsou dvojího druhu: Jedny směřují od západu na východ (budeme je nazývat ZV-ulice) a druhé směřují od jihu na sever (budeme je nazývat JS-ulice). Město, nebo přinejmenším jeho část, která je pro naší úlohu důležitá, má tvar obdélníka s N JS-ulicemi a M ZV-ulicemi. Jiřího dům stojí na rohu jedné z křižovatek a kino stojí na rohu jiné křižovatky.

Nezdá se ale, že by bylo účelné projíždět každou ulicí ve městě v celé její délce, proto Jiří volí následující strategii. V každé ulici ve městě projede vzdálenost alespoň jednoho bloku, to jest od jedné křižovatky na nejbližší, případně projede vzdálenost delší, nebude se ale v ulici obracet o vracet se po ní zpět. Každou ulici, jejíž část už projel, může později na některé z jejích křižovatek protnout, až bude projíždět ulicí kolmou na ní, nebude však do ní opět zabočovat a tedy ani už nepojede nějakým jiným jejím úsekem. Navíc, Jiří se během jízdy nechce vracet na startovní křižovatku a nechce přijet na cílovou křižovatku před skončením jízdy.

Situace je dále ještě nepatrně komplikována tím, že některé křižovatky ve městě jsou zcela neprůjezdné ze všech stran. Křižovatka u domu i u kina průjezdné jsou, lze tedy vyjet i případně dojet.

Jiří ví, že cesta od jedné křižovatky k sousední trvá vždy jednu minutu. Na to, aby dorazili z domu do kina, mají oba přátelé přesně T minut. Jiří chce tuto dobu vyčerpat celou, to jest nechce přijet ke kinu před vypršením této doby. Dobu nasedání a parkování apod zanedbáváme.

Předpokládáme, že ZV-ulice jsou číslovány od jihu počínaje 0 a JS-ulice jsou očíslovány od západu počínaje 0. Každá křižovatka má souřadnice [x, y], kde x udává číslo JS-ulice této křižovatky a y udává číslo ZV-ulice této křižovatky.

Obr. 1 Příklad. Schéma města s 8 JS-ulicemi a 7 ZV-ulicemi a červeně vyznačenými neprůjezdnými křižovatkami. Silnou čárou je vyznačena jedna z možných 1572 cest z domu (plný kroužek) do kina (prázdný kroužek) trvajících 45 minut.

Úloha
Máme zjistit, zda lze z domu dorazit do kina v čase právě T při strategii popsané výše, a pokud to jde, určit počet různých cest z domu do kina. Dvě cesty považujeme za různé, pokud se liší alespoň v jednom projetém úseku v některé z ulic.

Vstup

Na vstupu jsou tři řádky. První řádek obsahuje šest čísel. První dvě čísla jsou N a M udávající rozměr města. Třetí a čtvrté číslo představují x-ovou a y-souřadnici křižovatky, kde cesta městem začíná. Páté a šesté číslo představují x-ovou a y-souřadnici křižovatky, kde stojí kino a kde cesta městem má skončit.
Druhý řádek obsahuje seznam neprůjezdných křižovatek. Nejprve je uveden počet těchto křižovatek a poté je pro každou z nich uvedena její x a y souřadnice. Pokud je seznam neprůjezdných křižovatek prázdný, druhý řádek obsahuje jediné číslo 0.
Třetí řádek obsahuje jediné číslo představující počet minut trvání jízdy z domu do kina.
Všechna čísla na vstupu jsou celá a nezáporná, navzájem jsou na řádku oddělena jednou mezerou.
Můžeme předpokládat, že počet průjezdných křižovatek ve městě nepřesáhne 60.

Výstup

Na výstupu je jeden řádek s jedním celým číslem představujícím počet různých cest, jimiž lze za daný počet minut dojet od domu ke kinu při zachování podmínek úlohy.

Příklad 1

Vstup:

3 3 0 0 2 0
0
8

Výstup:

4

Obr. 2 Schéma města a odpovídající možné trasy podle zadání příkladu 1.

Příklad 2

Vstup:

4 4 0 0 3 2
0
11

Výstup:

6

Obr. 3 Schéma města a odpovídající možné trasy podle zadání příkladu 2.

Příklad 3

Vstup:

4 4 0 0 3 2
1 2 2
11

Výstup:

2

Obr. 4 Schéma města a odpovídající možné trasy podle zadání příkladu 3. Tento příklad se od předchozího liší pouze jednou neprůjezdnou křižovatkou.

Příklad 4

Vstup:

8 7 1 1 5 4
2 3 0 4 2
45

Výstup:

1572

Příklad 4 odpovídá ukázce z Obr. 1 v textu úlohy.

Veřejná data k úloze jsou k dispozici. Veřejná data jsou uložena také v odevzdávacím systému a při každém odevzdání/spuštění úlohy dostává řešitel kompletní výstup na stdout a stderr ze svého programu pro každý soubor veřejných dat.

Veřejná data