Revizia anterioară Revizia următoare
| Fișierul intrare/ieșire | stampile.in, stampile.out | Sursă | ad-hoc |
|---|---|---|---|
| Autor | CodeChef | Adăugată de |
Cătălin Frâncu
•
Catalin.Francu
|
| Timp de execuție pe test | 0.26 sec | Limită de memorie | 262144 KB |
| Scorul tău | N/A | Dificultate | N/A |
Poți vedea testele pentru această problemă accesând
atașamentele
.
Vezi soluțiile trimise | Statistici
Ștampile
Această problemă este copiată după Killing Zombies (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 Si ș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 Aj la Bj inclusiv. Ion poate vizita de mai multe ori același ghișeu pentru a obține mai multe ștampile, dar există o limită. După Vj 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.
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 S1, S2, ..., SN, separate prin spații. Pe următoarele M linii apar cîte trei numere Aj, Bj, Vj, separate prin spații, reprezentînd parametrii celor M ghișee.
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.
Restricții
- 1 ≤ N ≤ 200.000
- 1 ≤ M ≤ 200.000
- 1 ≤ Si ≤ 10.000 pentru 1 ≤ i ≤ N
- 1 ≤ Vj ≤ 10.000 pentru 1 ≤ j ≤ M
- 1 ≤ Aj ≤ Bj ≤ N pentru 1 ≤ j ≤ M
| puncte | restricții | |
|---|---|---|
| 1 | 25 | N, M ≤ 20; Vj = 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.
Exemplu
| 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 |
Explicații
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.
