Problem D
Vattenfall

Alexander gillar vatten. Då är det inte så konstigt att han är förtjust i vatten som forsar. Detta kanske är förklaringen till varför han vill skapa sitt eget vattenfall. Tänk bara, vatten som forsar i all oändlighet! Han har hittat en bergvägg som han tror kommer bli det perfekta vattenfallet efter att han har tillfört lite vatten. Bergväggen kan modelleras som ett $R \times C$ stort rutnät, där $N$ rutor har en klippa som sticker ut. Alexander tänker hälla ut vatten ovanifrån så att det flödar ner vatten i $K$ stycken kolumner. Vattnet sprider sig i rutnätet enligt följande regler: om rutan under vattnet är tom sprider det sig dit. Om det finns en klippa i vägen sprider det sig istället till höger och vänster. Om det finns en klippa ivägen till höger eller vänster sprider det sig inte i den riktningen. Alexander vill dock inte orsaka en översvämning, för då kommer allt vatten att så stilla till slut. Vatten som står stilla är självklart tråkigare än vatten som forsar. Därför vill han ha din hjälp att skriva ett program som räknar ut hur många kolumner som har vatten i sig i nedersta raden av klippan.

 

Figure 1: En illustration av flödet i exempelfall 1 och 2. Den röda ramen markerar slutet på bergsväggen.

Indata

Den första raden innehåller två heltal $R, C$ ($1 \le R, C \le 10^9$), antalet rader respektive kolumner som berget består av. Den andra innehåller två hetal $K, N$ ($1 \le K, N \le 10^5$), antalet kolumner med vatten i och antalet klippor som sticker ut ur berget.

Därefter följer $K$ rader, där den $i$:te rader innehåller en siffra $V_ i$ ($0 \le V_ i \le C-1$), som betyder att det strömmar ner vatten längs kolumn $V_ i$ från ovanför rutnätet. Det är garanterat att alla $V_ i$ är unika.

Därefter följer $N$ rader, där den $i$:te rader innehåller två heltal $A_ i$ ($1 \le A_ i \le R-1$) och $B_ i$ ($0 \le B_ i \le C-1$), raden och kolumnen där den $i$:te klippan finns. Även dessa är unika. Notera att i detta problem är rad $0$ raden längst ner och att denna garanteras vara klippfri.

Utdata

Skriv ut ett heltal: antalet kolumner som innehåller vatten i nedersta raden av rutnätet.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

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

3

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

1

5 4
1 3
3
1 1
2 2
3 3

1