== include(page="template/taskheader" task_id="stampile") ==
bq. Această problemă este copiată după "Killing Zombies":https://www.codechef.com/problems/CLKLZM (Code Chef). Testele sînt noi.
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.
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.
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.
h2. Date de intrare
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.
Fișierul de intrare $stampile.in$ ...
h2. Date de ieșire
Î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.
În fișierul de ieșire $stampile.out$ ...
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$
table(subtasks).
|_. # |_. puncte |_. restricții |
| 1 | 25 | $N$, $M$ ≤ 20; $V[~j~]$ = 1 pentru 1 ≤ $j$ ≤ $M$ |
| 2 | 25 | $N$, $M$ ≤ 10.000 |
| 3 | 25 | $N$, $M$ ≤ 100.000 |
| 4 | 25 | Fără restricții suplimentare. |
*Notă:* La concursul de selecție, punctajele pentru subtaskuri au fost 15, 23, 29 respectiv 33.
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example).
|_. stampile.in |_. stampile.out |
| 5 5
1 2 3 4 5
2 4 3
1 5 1
3 5 3
1 2 3
4 5 3
| 6
|
| 3 2
2 5 2
1 2 2
2 3 2
| -1
|
h3. Explicații
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
Pentru primul exemplu, o soluție ar fi: cîte o vizită la ghișeele 1 și 2 și cîte două vizite la ghișeele 3 și 5.
h3. Explicație
Pentru al doilea exemplu, Ion nu poate aduna mai mult de 4 ștampile pe pagina 2.
...
== include(page="template/taskfooter" task_id="stampile") ==
