Fişierul intrare/ieşire:	spectacole.in, spectacole.out	Sursă	Algoritmiada 2015 Runda 1
Autor	Marius Dumitran, Teodor Plop	Adăugată de	Teodor Plop •Teodor94
Timp execuţie pe test	0.325 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Spectacole

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-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 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.

Date de intrare

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₁, A₂, ..., respectiv A_N. Al treilea rand va contine inca N numere reprezentand valorile B₁, B₂, ..., 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.

Date de ieşire

În fişierul de ieşire spectacole.out se va găsi un singur număr natural, reprezentând numărul maxim de spectacole pe care le poate vedea Antonio, respectând regulile de mai sus.

Restricţii

• 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

Exemplu

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.

Cum se trimit solutii?