== include(page="template/taskheader" task_id="stampile") ==
Ion vrea să-și plătească taxele. Pentru aceasta, a pregătit un document cu @N@ pagini, cu care s-a dus la ANAF. Pentru ca ANAF să-i accepte documentul, pe fiecare pagină @i@ (1 ≤ @i@ ≤ @N@) trebuie să apară cel puțin S[~i~] ștampile.
Ion vrea să-și plătească taxele. Pentru aceasta, a pregătit un document cu @N@ pagini, cu care s-a dus la ANAF. Pentru ca ANAF să-i accepte documentul, pe fiecare pagină @i@ (1 ≤ @i@ ≤ @N@) trebuie să apară cel puțin $S[~i~]$ ștampile.
La ANAF sînt M ghis, ee. Printr-o vizită la ghis, eul j (1 ≤ j ≤ M ), Ion obt, ine cîte o s, tampilă pe paginile de la Aj la Bj inclusiv. Ion poate vizita de mai multe ori acelas, i ghis, eu pentru a obt, ine mai multe s, tampile, dar există o limită. După Vj vizite, funct, ionarul de la ghis, eul j se enervează s, i închide ghis, eul.
La ANAF sînt @M@ ghișee. Printr-o vizită la ghișeul @j@ (1 ≤ @j@ ≤ @M@), Ion obține cîte o ștampilă pe paginile de la $A[~j~]$ la $B[~j~]$ inclusiv. Ion poate vizita de mai multe ori același ghișeu pentru a obține mai multe ștampile, dar există o limită. După $V[~j~]$ vizite, funcționarul de la ghișeul $j$ se enervează și închide ghișeul.
Ajutat, i-l pe Ion să afle dacă îs, i poate plăti taxele, iar în caz afirmativ, care este numărul minim necesar de vizite la ghis, ee.
Ajutați-l pe Ion să afle dacă își poate plăti taxele, iar în caz afirmativ, care este numărul minim necesar de vizite la ghișee.
h2. Date de intrare
Fișierul de intrare $stampile.in$ ...
Fișierul de intrare $stampile.in$ conține pe prima linie numerele @N@ și @M@, separate prin spațiu. A doua linie conține numerele $S[~1~]$, $S[~2~]$, ..., $S[~N~]$, separate prin spații. Pe următoarele @M@ linii apar cîte trei numere $A[~j~]$, $B[~j~]$, $V[~j~]$, separate prin spații, reprezentînd parametrii celor @M@ ghișee.
h2. Date de ieșire
În fișierul de ieșire $stampile.out$ ...
În fișierul de ieșire $stampile.out$ tipăriți un singur număr. Dacă există un mod de a obține toate ștampilele, tipăriți numărul minim de vizite necesare. În caz contrar, tipăriți −1.
h2. Restricții
* $... ≤ ... ≤ ...$
* 1 ≤ $N$ ≤ 200.000
* 1 ≤ $M$ ≤ 200.000
* 1 ≤ $S[~i~]$ ≤ 10.000 pentru 1 ≤ $i$ ≤ $N$
* 1 ≤ $V[~j~]$ ≤ 10.000 pentru 1 ≤ $j$ ≤ $M$
* 1 ≤ $A[~j~]$ ≤ $B[~j~]$ ≤ N pentru 1 ≤ $j$ ≤ $M$
h2. Exemplu
