Snömurskontrollant

PO-juryn kan inte programmera. Efter fiaskot i onlinekvalet, där den trasiga domaren för problemet Snömur råkade ge Island vinsten med 211.58 av 100 poäng på problemet har juryn bestämt sig för att outsource:a sina domare till folk som faktiskt kan koda – PO-finalister.

Problemet var som följer:

Sverige ska bygga en snömur, av en viss bredd $W$. Som byggmaterial finns det ett antal snöblock som alla har höjden 1, men kan ha olika bredder. När muren konstrueras måste varje block uppfylla följande regel: på raden under blocket, på de två positioner blocket har sina ändpunkter, måste det ligga ett block precis till höger och vänster om punkten, undantaget början och slutet på en rad, där det istället måste finnas en ändpunkt på varje rad (se den vänstra, näst översta muren i Figur 1 där detta saknas på översta raden).

Det får dessutom inte finnas hålrum på samma position på två direkt efterföljande rader i muren (den tomma raden precis ovanför muren räknas inte).

Följande bild illustrerar några otillåtna (vänster) och tillåtna (höger) murar:

\includegraphics[width=0.7\textwidth ]{mur.png}
Figure 1: Ett antal otillåtna (vänster) och tillåtna (höger) murar.

Givet ett förslag på hur muren ska se ut, avgör om muren är en tillåten mur.

Indata

Den första raden innehåller två heltal $W$ och $H$ - bredden och höjden på muren.

De följande $H$ raderna beskriver raderna i muren. Varje rad börjar med ett heltal $B \ge 1$, antalet block på raden. Detta följs av $B$ par av heltal $P_ j, L_ j$, den (noll-indexerade) positionen och längden för det $j$:te blocket på raden. Dessa kommer ges i stigande $P_ j$-ordning, d.v.s från vänster till höger. Inga block kommer överlappa eller ligga utanför muren.

Raderna är givna underifrån - dvs den första raden i indata är den understa raden i muren.

Låt summan av antalet block över alla rader vara $N$. Detta tal har gränser i poängsättningstabellen.

Utdata

Du ska skriva ut YES om muren är tillåten, och NO om den inte är det.

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.

Grupp

Poängvärde

Gränser

Övrigt

1

31

$1 \le N, W, H \le 100\, 000$

Inga hål förekommer direkt över ett annat hål

2

34

$1 \le N, W, H \le 1\, 000$

 

3

35

$1 \le N, W, H \le 100\, 000$

 

Förklaring av exempel

De fyra första exemplen motsvarar de fyra otillåtna murarna till vänster i bilden. De sista fyra exemplen motsvarar de fyra tillåtna murarna till höger i bilden.

Sample Input 1 Sample Output 1
10 3
1 0 10
2 0 4 6 4
2 0 3 7 3
NO
Sample Input 2 Sample Output 2
10 3
1 0 10
2 0 4 6 4
1 0 9
NO
Sample Input 3 Sample Output 3
10 3
1 0 10
2 0 4 6 4
2 0 5 5 5
NO
Sample Input 4 Sample Output 4
10 3
1 0 10
2 0 4 6 4
2 0 4 4 6
NO
Sample Input 5 Sample Output 5
10 3
1 0 10
2 0 4 6 4
1 0 10
YES
Sample Input 6 Sample Output 6
10 3
1 0 10
2 0 4 6 4
2 0 7 8 2
YES
Sample Input 7 Sample Output 7
10 3
2 0 2 3 7
2 0 4 6 4
1 0 10
YES
Sample Input 8 Sample Output 8
10 3
1 0 10
3 0 4 4 2 9 1
2 0 4 4 6
YES