_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-o sală centrală, iar drumurile din această sală centrală spre o sală de spectacol şi drumurile inverse nu sunt identice. Mai exact durata de deplasare dinspre sala cu numarul $i$ si sala centrală este $A{~i~}$, iar dinspre sala centrală spre sala i este $B{~i~}$. Nu exista altă metoda pentru Antonio să se deplaseze între 2 sali $i$ şi $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 != 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 ≤ 1.000$
* $1 ≤ K[i] ≤ 1.000$
* $0 ≤ a ≤ b ≤ 24 * 60 = 1440$
* $0 ≤ T ≤ 1440$

* $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 ≤ 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
table(example). |_. spectacole.in |_. spectacole.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 2 4
2 2
3 3
1 0 5
1 5 13
2 10 15
2 15 20
| 3

|
h3. Explicaţie

...

Antonio va viziona primul spectacol care are loc in sala $1$. La momentul de timp $5$ va pleca către sala $2$, unde va viziona spectacolele $3$ si $4$.

== include(page="template/taskfooter" task_id="spectacole") ==