_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 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:

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.

* $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

* $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 |

| 2 5
2
0 5
5 13
2
10 15
15 20

| 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 din sala $1$. La momentul de timp $5$ va pleca către sala $2$, unde va viziona primele două spectacole.

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") ==