Freakcoins P23949

Ens trobem a la meravellosa ciutat de París, gaudint d’un relaxat passeig per la ciutat… si no fos pel nostre guia turístic, en Gerard. Per evitar que ens faci veure tants monuments, hem dissenyat una moneda imaginària, el FreakCoin, amb la qual ens ha de pagar per cada desplaçament que fem. I en Gerard només pot aconseguir FreakCoins comprant-nos menjar!

Inicialment ens trobem al punt número 0, i en Gerard té 0 FreakCoins. Vol visitar $n$ punts diferents en un ordre predeterminat, i sap que anar de $i$ a $i+1$ li costarà $a_i$ FreakCoins. També té informació d’$m$ boulangeries: per a cadascuna, a quin punt $x_i$ es troba, quants FreakCoins $f_i$ tindrà si hi compra menjar allà, i el preu $p_i$ en euros de comprar-hi menjar. Quin és el mínim nombre d’euros que s’haurà de gastar per poder visitar els $n$ monuments?

Tingueu en compte que en un punt hi pot haver zero, una, o més boulangeries. A més, els FreakCoins no s’acumulen. És a dir, en tot moment es tenen tants FreakCoins com els obtinguts a l’última boulangerie on es va comprar, menys els que s’han gastat ens els desplaçaments posteriors. Lògicament, el nombre de FreakCoins no pot ser mai negatiu.

Entrada

L’entrada consisteix en diversos casos, només amb nombres naturals. Cada cas comença amb $n$ i $m$. Segueixen els $n$ $a_i$’s. Finalment, tenim $m$ triplets $x_i$ $f_i$ $p_i$. Suposeu $2 \le n \le 10^5$, $1 \le m \le 10^5$, $1 \le a_i \le 10^4$, $0 \le x_i < n$, $1 \le f_i \le 10^9$, i $1 \le p_i \le 10^4$.

Sortida

Per a cada cas, escriviu la mínima quantitat d’euros necessaris per poder visitar els $n$ llocs. Si no és possible, escriviu $-1$.