Freakcoins P23949


Statement
 

pdf   zip

thehtml

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à ai FreakCoins. També té informació d’m boulangeries: per a cadascuna, a quin punt xi es troba, quants FreakCoins fi tindrà si hi compra menjar allà, i el preu pi 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 ai’s. Finalment, tenim m triplets xi fi pi. Suposeu 2 ≤ n ≤ 105, 1 ≤ m ≤ 105, 1 ≤ ai ≤ 104, 0 ≤ xi < n, 1 ≤ fi ≤ 109, i 1 ≤ pi ≤ 104.

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.

Public test cases
  • Input

    3 2
    5 5 5
    0 14 6  1 10 3
    
    3 2
    1 2 3
    1 4 8  0 3 9
    

    Output

    9
    -1
    
  • Information
    Author
    Cesc Folch
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++