_Până şi Antonio a auzit de problema spectacolelor. Fiind însă o problemă deja foarte bine cunoscută şi mult prea "clasică" pentru gusturile lui Antonio, acesta vă propune să rezolvaţi următoarea problema a spectacolelor. Succes!_
Se dau $N$ săli de spectacole. Pentru fiecare sală $i$ din cele $N$ săli, se cunoaşte numărul de spectacole care rulează în ziua de astăzi, $K[i]$, şi $K[i]$ perechi de câte două numere naturale $(a, b)$, reprezentând timpul de început al spectacolului, respectiv timpul de sfârşit. Se ştie că distanţa de timp între oricare două săli $i$ şi $j$ din cele $N$, cu $i$ diferit de $j$, este egală cu un număr natural $T$. Antonio vrea să vadă cât mai multe spectacole, respectând următoarele reguli:
Se dau $N$ săli de spectacole si $M$ spectacole. Pentru fiecare din cele $M$ spectacole se dau $3$ numere $s{~i~}$, $x{~i~}$ si $y{~i~}$ reprezentând sala unde se ţine spectacolul, timpul de început, respectiv timpul de sfârşit. Se ştie că pentru a se deplasa intre sali Antonio trebuie sa se deplaseze printr-un punct central, iar drumurule din acest punct central spre o sala si inapoi nu sunt identice. Mai exact durata de deplasare dinspre sala cu numarul $i$ si punctul central este $A{~i~}$, iar dinspre punctul central spre sala i este $B{~i~}$. Nu exista alta metoda pentru Antonio sa se deplaseze intre 2 sali $i$ si $j$, astfel pentru a se deplasa de la sala $i$ la sala $j$ Antonio are nevoie de $A{~i~} + B{~j~}$ momente de timp. Antonio vrea să vadă cât mai multe spectacole, respectând următoarele reguli:
* Antonio va vedea doar spectacole complete. Altfel spus, Antonio nu are voie să părăsească sala decât în momentul terminării spectacolului.
* Dacă Antonio se află în sala $i$ vizionând un spectacol care se termină la momentul de timp $B$, acesta are în continuare două opţiuni:
** Poate rămâne în sala $i$, urmând să vizioneze după bunul său plac orice spectacol care începe la un moment de timp mai mare sau egal decât $B$.
** Poate pleca la momentul $B$ către oricare sală $j (i diferit de j)$, ajungând în sala $j$ la momentul de timp $B + T$. Astfel, acesta poate viziona orice spectacol care rulează în sala $j$ şi are timpul de început mai mare sau egal cu $B + T$.
* Dacă Antonio se află în sala $i$ vizionând un spectacol care se termină la momentul de timp $T$, acesta are în continuare două opţiuni:
** Poate rămâne în sala $i$, urmând să vizioneze după bunul său plac orice spectacol care începe la un moment de timp mai mare sau egal decât $T$.
** Poate pleca la momentul $T$ către oricare sală $j (i diferit de j)$, ajungând în sala $j$ la momentul de timp $T + A{~i~} + B{~j~}$. Astfel, acesta poate viziona orice spectacol care rulează în sala $j$ şi are timpul de început mai mare sau egal cu $T + A{~i~} + B{~j~}$.
h2. Date de intrare
Fişierul de intrare $spectacole.in$ conţine două numere naturale $N$ şi $T$, reprezentând numărul sălilor de spectacol, respectiv distanţa de timp între oricare două săli distincte. Pentru fiecare sală $i$ din cele $N$, pe prima linie se va găsi un număr natural $K[i]$, reprezentând numărul de spectacole ce rulează în sala $i$, urmat de $K[i]$ linii. Pe fiecare linie $j$ din aceste $K[i]$ linii se va găsi o pereche $(a, b)$, reprezentând timpul de start şi timpul de final al spectacolului $j$ din sala $i$.
Fişierul de intrare $spectacole.in$ conţine două numere naturale $N$ şi $M$, reprezentând numărul sălilor de spectacol, respectiv numarul de spectacole. Urmatorul rand va contine $N$ numere reprezentand valorile $A{~1~}$, $A{~2~}$, ..., respectiv $A{~N~}$. Al treilea rand va contine inca $N$ numere reprezentand valorile $B{~1~}$, $B{~2~}$, ..., respectiv $B{~N~}$.
Urmatoarele $M$ linii vor contine cate $3$ valori intregi fiecare. A $i$-a dintre aceste linii va contine valorile $s{~i~}$, $x{~i~}$ si $y{~i~}$.
h2. Date de ieşire
h2. Restricţii
* $1 ≤ N ≤ 100$
* $1 ≤ K[i] ≤ 100$
* $0 ≤ a < b ≤ 24 * 60 = 1.440$
* $0 ≤ T ≤ 1.440$
* $1 ≤ N ≤ 2000$
* $1 ≤ M ≤ 20000$
* $1 ≤ s{~i~} ≤ N$
* $0 ≤ x{~i~} < y{~i~} ≤ 1.000.000.000$
* $0 ≤ A{~i~}, B{~i~} ≤ 1.000.000.000$
* $Se garantează că nu există două spectacole care să ruleze simultan în aceeaşi sală.$
* $Pentru teste in valoare de *30* de puncte *N ≤ 100* si y{~i~} ≤ 1.250$
* $Pentru teste in valoare de inca *20* de puncte *N &le 500* si y{~i~} ≤ 1.250$
* $Pentru teste in valoare de *20* de puncte (dar nu neaparat altele decat cele 30 + 20 de mai sus) A{~i~} = B{~i~} = 0
h2. Exemplu
