Duž jednog puta koji je prav nalazi se Tomina kuća. Duž tog puta nalazi se i n svetiljki, svaka sa

• određenom koordinatom,
• dometom osvetljavanja

• potrošnjom u jedninici vremena.

  Tomina kuća ima koordinatu 0. Koordinata svetiljke označava poziciju svetiljke u odnosu na Tominu kuću. Ukoliko je koordinata svetiljke neki broj x tada se

• ukoliko je x broj veći ili jednak 0 svetiljka nalazi x metara desno od Tomine kuće

• ukoliko je x manje od 0 svetiljka nalazi x metara levo od Tomine kuće

Domet osvetljavanja neke svetiljka je broj koji označava kolikometara levo i desno od te svetiljke je put osvetljen pomoću nje. Ukoliko je domet neke svetiljke neko x a njena koordinata neko y put je od kordinate y-x do y+x osvetljen pomoću te svetiljke.

Potrošnja u jedinici vremena neke svetiljke je broj kojioznačava koliko džula energije u jedinici vremena troši tasvetiljka kada je upaljena.

Na početku su sve svetiljke ugašene. Toma želi, tako štoće upaliti neke svetiljke, da osvetli put u kontinuitetu odkoordinate A do koordinate B (A<B) tako da potrošnjaenergije u jedinici vremena bude minimalna.

(Toma želi samo da sve tačke puta počev od tačke sakoordinatom A do tačke sa koordinatom B budu osvetljene, nezanima ga da li će još neki delovi puta koji su izvan ovogintervala biti osvetljeni)

Ulaz:

(Ulazni podaci se učitavaju sa standardnog ulaza) U prvom redu tekstualne datoteke nalaze seredom brojevi n, A i B ( n je prirodan broj manji ilijednak 10⁵ dok su A i B celi brojevi koji su veći ilijednaki -2x10⁹ i manji ili jednaki 2x10⁹ iA<B) U svakom od sledećih n redova nalaze se po tri celabroja koji opisuju jednu svetiljku. Ti brojevi su redom koordinatasvetiljke (ceo broj veći ili jednak -10⁹ i manji ili jednak10⁹), domet osvetljavanja (prirodan broj manji ili jednak10⁹) i potrošnja u jedinici vremena (prirodan broj manji ilijednak 20000). (U redu čiji je redni broj i+1 nalazi se opisi-te svetiljke)

Izlaz:

(Izlazni podaci se ispisuju na standardni izlaz) U izlaznoj datoteci treba upisati broj kojioznačava minimalnu potrošnju energije u jedinici vremena koja semora potrošiti da bi se osvetlio deo puta koji Toma želi ukolikoje to moguće. Ukoliko to nije moguće upisati -1.

U 50% test primera n je manje ili jednako 5000.

Primer 1:

6 -10 20
-8 4 2
25 4 7
3 10 1
0 15 4
17 3 5
16 4 2

5

Objašnjenje.

Moguće je osvetliti deo puta od koordinate -10 do koordinate20. Minimalna potrošnja energije u jedinici vremena koja semora imati da bi se do izvelo je 5 i ona se dobija paljenjem 1. ,3. i 6. svetiljke. (1. svetiljka osvetljava interval od -12 do-4 , 3. svetiljka osvetljava interval od -7 do 13 a 6.svetiljka osvetljava interval od 12 od 20)

Primer 2:

3 4 20
8 5 10
8 4 7
19 4 10

-1