Diferențe pentru problema/stampile între reviziile #3 si #8

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

bq. Această problemă este copiată după "Killing Zombies":https://www.codechef.com/problems/CLKLZM (Code Chef). Testele sînt noi.

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.

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

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

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

| 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

h3. Explicație

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.

...

Pentru al doilea exemplu, Ion nu poate aduna mai mult de 4 ștampile pe pagina 2.

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