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 ≤ n ≤ 10⁵, 1 ≤ m ≤ 10⁵, 1 ≤ a_i ≤ 10⁴, 0 ≤ x_i < n, 1 ≤ f_i ≤ 10⁹, i 1 ≤ p_i ≤ 10⁴.

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.