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

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.

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₁, S₂, ..., 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.

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

Notă: La concursul de selecție, punctajele pentru subtaskuri au fost 15, 23, 29 respectiv 33.

Exemplu

Explicație

...